Dijkstra最短路径算法

求解最短路径问题

给定图G=(V(G),E(G))以及V(G)中的一对顶点u和v，我们可以把u到v的距离定义为u到v的一条边数最少的路径。用记号d(u,v)来表示这个距离。于是距离问题就是计算给定图G的d(u,v)以及两个特定的顶点u和v。

例如本图，如不考虑图上各点之间的距离，即各点之间的距离为1.则d(u,y)=2，即经过w点后到达y点的距离。若考虑各点之间的距离为图上的距离，则G中最短路径为u经过v、w两个节点z之后的长度，即1+2+3=6。因此，d(i,j)只考虑i和j间边的数目，而最短路径要考虑边的长度。

为了更简单理解最短路径的求法，我们需要一个物理类比。假设如上图所示，图中有u和y，以及每条边的边长。我们要以细绳为模型。假设上图中每个节点为细绳与细绳之间所打的结，而节点间的距离为边的权重(不管单位是米还是毫米，统一即可)，细绳即是边。我们为了求u和y的最短路径，可以将细绳的u和y两个结拉紧，此时u和y的最短路径为此时绳的长度，中间的结即所经过的节点。

Dijkstra求最短路径算法

输入	图G=(V(G),E(G))有一个源顶点s和一个汇顶点t，以及对所有的边ij∈E(G)的非负边长cij。
输出	G中从s到t的最短路径的长度
第0步	从对每个顶点做临时标记L开始，做法如下：L(s)=0,且对除s外所有的顶点L(i)=∞
第1步	找带有最小临时标记的顶点(如果有结，随机的取一个)。使该标记变成永久标记，即该标记不再改变
第2步	对每个没有永久标记但是又带有永久标记的顶点相邻的顶点j，按如下方法计算一个新的临时标记:L(j)=min{L(i)+cij}，求最小是对所有带有永久标记的顶点i做的。重复第1步和第2步，直到所有的顶点都打上了永久标记为止。

matlab代码求解上图u,y距离

%inf代表该点与其他点的距离为inf
%   v     w    y     u     x     z  
W=[inf    2   inf    1    inf   inf  ;  %v
    2    inf   3     7     8    inf  ;  %w
   inf    3   inf   inf   inf    4   ;  %y
    1     7   inf   inf    6    inf  ;  %u
   inf    8   inf    6    inf    6   ;  %x
   inf   inf   4    inf    6    inf  ;];%z
[distance,path]=Dijk(W,4,3);

function [ distance path] = Dijk( W,st,e )
%DIJK Summary of this function goes here
%   W  权值矩阵   st 搜索的起点   e 搜索的终点
n=length(W);%节点数
D = W(st,:);
visit= ones(1:n); visit(st)=0;
parent = zeros(1,n);%记录每个节点的上一个节点
 
path =[];
 
for i=1:n-1
    temp = [];
    %从起点出发，找最短距离的下一个点，每次不会重复原来的轨迹，设置visit判断节点是否访问
    for j=1:n
       if visit(j)
           temp =[temp D(j)];
       else
           temp =[temp inf];
       end
       
    end
    
    [value,index] = min(temp);
   
    visit(index) = 0;
    
    %更新 如果经过index节点，从起点到每个节点的路径长度更小，则更新，记录前趋节点，方便后面回溯循迹
    for k=1:n
        if D(k)>D(index)+W(index,k)
           D(k) = D(index)+W(index,k);
           parent(k) = index;
        end
    end
    
   
end
 
distance = D(e);%最短距离
%回溯法  从尾部往前寻找搜索路径
t = e;
while t~=st && t>0
 path =[t,path];
  p=parent(t);t=p;
end
path =[st,path];%最短路径
 
end

>> Dijk(W, 4, 3)
ans =
     6