fengguanxi / dijkstrashortesetpath

Dijkstra最短路径算法

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