来自NOCOW

跳转到：导航, 搜索

 这篇文章可以证实是由NOCOW用户原创，不存在任何版权争议。
 本文作者同意以GNU FDL、CC-by-sa和GNU LGPL（如果适用）三种版权发布此文章（不包括翻译文章中属于原始所有者的部分版权）。
 如果你修改了这篇文章并且不同意用GNU FDL以外的版权发布，可以换一个版权模板或者移除此模板。

Dijkstra算法是一种求单源最短路的算法，即从一个点开始到所有其他点的最短路。其基本原理是：每次新扩展一个距离最短的点，更新与其相邻的点的距离。当所有边权都为正时，由于不会存在一个距离更短的没扩展过的点，所以这个点的距离永远不会再被改变，因而保证了算法的正确性。不过根据这个原理，用Dijkstra求最短路的图不能有负权边，因为扩展到负权边的时候会产生更短的距离，有可能就破坏了已经更新的点距离不会改变的性质。

如果用本算法求一个图中全部的最短路，则要以每个点为源调用一次Dijkstra算法。

[编辑] 适用条件与限制

有向图和无向图都可以使用本算法，无向图中的每条边可以看成相反的两条边。
用来求最短路的图中不能存在负权边。(可以利用拓扑排序检测)

[编辑] 算法流程

在以下说明中，s为源，w[u,v]为点u和v之间的边的长度，结果保存在dist[]

初始化：源的距离dist[s]设为0，其他的点距离设为无穷大，同时把所有的点的状态设为没有扩展过。
循环n-1次：
1. 在没有扩展过的点中取一距离最小的点u，并将其状态设为已扩展。
2. 对于每个与u相邻的点v，执行Relax(u,v)，也就是说，如果dist[u]+w[u,v]<dist[v]，那么把dist[v]更新成更短的距离dist[u]+w[u,v]。此时到点v的最短路径上，前一个节点即为u。
结束。此时对于任意的u，dist[u]就是s到u的距离。

[编辑] 算法实现

  function [min,path]=dijkstra(w,start,terminal)
  n=size(w,1); label(start)=0; f(start)=start;
  for i=1:n
     if i~=start
        label(i)=inf;
     end
  end
  s(1)=start; u=start;
  while length(s)<n
     for i=1:n
        ins=0;
        for j=1:length(s)
           if i==s(j)
              ins=1;
           end
        end
        if ins==0
           v=i;
           if label(v)>(label(u)+w(u,v))
              label(v)=(label(u)+w(u,v)); f(v)=u;
           end
        end
     end
     v1=0;
     k=inf;
     for i=1:n
        ins=0;
        for j=1:length(s)
           if i==s(j)
              ins=1;
           end
        end
        if ins==0
           v=i;
           if k>label(v)
              k=label(v);  v1=v;
           end
        end
     end
     s(length(s)+1)=v1;  
     u=v1;
  end
  min=label(terminal); path(1)=terminal;
  i=1; 
  while path(i)~=start
     path(i+1)=f(path(i));
     i=i+1 ;
  end
  path(i)=start;
  L=length(path);
  path=path(L:-1:1);

调用

  edge= [ 2,3,1,3,3,5,4, 4,1,7,6,6,5, 5,11, 1,8,6,9,10,8,9, 9,10;...
             3,4,2,7,5,3,5,11,7,6,7,5,6,11, 5, 8,1,9,5,11,9,8,10,9;...
             3,5,8,5,6,6,1,12,7,9,9,2,2,10,10,8,8,3,7, 2, 9,9, 2, 2];
  n=11; weight=inf*ones(n, n);
  for i=1:n
     weight(i, i)=0;
  end
  for i=1:size(edge,2)
     weight(edge(1, i), edge(2, i))=edge(3, i);
  end
  [dis, path]=dijkstra(weight, 1, 11)