Dijkstra最短路径代码使用说明
首先这份源码有缺陷,Dijkstra可以做有向图和无向图(两者都不能含有带负权值的成圈路径),但是这份代码只能做无向图的最短路径。
首先是要明白global的用法: MATLAB中如果要使用global变量(即全局变量),首先要在主函数中声明:
clc,clear;
global D;
D=[0,2,1,4,5,1;
2,0,4,2,3,4;
1,4,0,1,2,4;
4,2,1,0,3,3;
5,3,2,3,0,1;
1,4,4,3,1,0];
然后在函数中声明:
global D;
pb(1:length(D))=0;
在明白global的用法之后,再讲一下length函数. length函数是一个矩阵(M*N大小)中M和N之间的最大值,由于有向图之间肯定是各点到各点的距离(不能直接到到达的也得用一个超级大的数字表示),所以这里矩阵肯定是个方阵.
下面我们直接展示源码了:
clc,clear;
global D;
D=[0,2,1,4,5,1;
2,0,4,2,3,4;
1,4,0,1,2,4;
4,2,1,0,3,3;
5,3,2,3,0,1;
1,4,4,3,1,0];
[d,index2] = Dijkstra(1)
function [d,index2] = Dijkstra(s)%s为源点 返回: d最短路向量 index2前驱向量
global D;
pb(1:length(D))=0;
pb(s)=1; %当一个点已经求出到原点的最短距离时,其下标i对应的pb(i)赋1
index1=s; %存放存入S集合的顺序
index2=ones(1,length(D))*-1; %存放始点到第i点最短通路中第i顶点前一顶点的序号
d(1:length(D))=inf;
d(s)=0; %存放由始点到第i点最短通路的值
temp=s; %temp表示s,算s到其它点的最短路。
while sum(pb)<length(D) %看是否所有的点都标记为P标号
tb=find(pb==0); %找到标号为0的所有点,即找到还没有存入S的点
d(tb)=min(d(tb),d(temp)+D(temp,tb));%计算标号为0的点的最短路,或者是从原点直接到这个点,又或者是原点经过r1,间接到达这个点
tmpb=find(d(tb)==min(d(tb))); %求d[tb]序列最小值的下标
temp=tb(tmpb(1));%可能有多条路径同时到达最小值,取其中一个,temp也从原点变为下一个点
pb(temp)=1;%找到最小路径的表对应的pb(i)=1
index1=[index1,temp]; %存放存入S集合的顺序
temp2=find(d(index1)==d(temp)-D(temp,index1));
index2(temp)=index1(temp2(1)); %记录标号索引
end
end
输入的是一个整形数字,范围在1到length(D)(这里的length(D)为6),这个整形数字的意思是源点,如果取1,意思即是求a到其他所有点的最短距离(我们这里假设第一行就对应a)。另外还需注意,Dijkstra算法可用来求有向图和无向图的最短距离(无论是有向还是无向都不能含有权值为负的路径)。这里D方阵的第一行:0,2,1,4,5,1 ,意思就是a到a的距离为0,到b的直接距离为2,到c的直接距离为1,等等。因为是有向图,所以a到b的距离与b到a的距离可以不相等(实例中,a到b为2,b到a为1)。
我们再看一下输出结果,假设源点为1(即a),那么经手工计算,路径与距离分别为 a,b=2 a,c=1 a,c,d=2 a,f,e=2, a,f=1
我们再看一下代码的输出结果:
d =
0 2 1 2 2 1
index2 =
-1 1 1 3 6 1
d是代表距离,即a到a的最短距离为0,a到b的最短距离为2 index2代表路径,存放始点到第i点最短通路中第i顶点前一顶点的序号,举个例子: a到b的index2为1,意思是a到b的最短路径中,到达终点b之前的上一个站点是a,即a直接到b a到d的index2的对应值是3,即a到d的最短路径中,到达终点之前的上一个站点是c,然后再转到a到c的最短路径中,到c之前的上一个站点是a,所以直接是a,c.那么a到d的最短路径是a,c,d=2