1. Dijkstra算法
Dijkstra算法的基本思想：从起始点出发，每次找到离源点最近的一个顶点，然后以这个顶点为中心进行扩展，每向外延伸一步都要求是最短的，直至覆盖所有顶点，最终得到源点到其余所有点的最短路径。
算法过程如下：
输入：带权图G=(V,E)，指定起点s∈V，边(i,j)的权值为w(i ,j)＞0。
输出：每个顶点v标注(l (v ),p (v))，其中：l(v)是从s到v的最短路径长度；p(v)是该路径上v的前一个顶点。
第一步：将所有顶点分组，永久性标号组P和临时性标号组V-P，显然，开始只有起点s作永久性标记，并且l(s)=0，其他点都作临时性标记，并且l(s)=∞，对于所有点，都有p (v)=null 。
第二步：对∀v ∈(V -P)，比较l(v)与l (u)+w( u ,v)的值（其中u为新加入P中的点）。如果l (u)+w( u ,v) ＜l(v)，将v的标记更新为(l (u )+w( u ,v ),u)，即l (v)=min{l (v ),l (u )+w( u ,v)}。也就是说，找到其他点与u的最短距离并更新。
第三步：找出T=V-P中带有最小临时标记的顶点v（如果有多个点，则任选一个），并更新为永久性标记，即P=P∪{v}。
第四步：重复步骤2和3，直至V-P=∅为止，此时所有顶点均标上了永久性标号。
例1 如图3.2.1所示的交通网络，每条弧上的数字代表车辆在该路段行驶所需的时间，若有一批货物要从顶点s运往顶点e，问运货车应沿哪条线路行驶，才能最快地到达目的地？
图3.2.1(www.xing528.com)
解 应用Dijkstra算法，计算过程如表3.2.1所示。
表3.2.1 Dijkstra算法过程
2. Dijkstra算法的MATLAB代码
用矩阵表示各个顶点间的相邻关系，行向量pb用来存放顶点标号信息，0和1分别表示顶点的临时性及永久性标记；d用来存放各点最短距离；path用来存放各点最短路径的上一点标号。
MATLAB程序如下：
pb(1: length(a))=0; pb(temp)=1; %求出最短路径的点作永久性标记1，未求出的作临时性标记0
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
