单源最短路径在这个问题中，给出有向图G，它的每条边都有一个非负的长度（耗费）aij，路径的长度即为此路径所经过的边的长度之和。对于给定的源顶点s，需找出从它到图中其他任意顶点（称为目的）的最短路径。图1310a给出了一个具有五个顶点的有向图，各边上的数即为长度。假设源顶点s为1，从顶点1出发的最短路径按路径长度顺序列在图1310b中，每条路径前面的数字为路径的长度。利用EDijkstra发明的贪婪算法可以解决最短路径问题，它通过分步方法求出最短路径。每一步产生一个到达新的目的顶点的最短路径。下一步所能达到的目的顶点通过如下贪婪准则选取：在还未产生最短路径的顶点中，选择路径长度最短的目的顶点。也就是说，Dijkstra的方法按路径长度顺序产生最短路径。首先最初产生从s到它自身的路径，这条路径没有边，其长度为0。在贪婪算法的每一步中，产生下一个最短路径。一种方法是在目前已产生的最短路径中加入一条可行的最短的边，结果产生的新路径是原先产生的最短路径加上一条边。这种策略并不总是起作用。另一种方法是在目前产生的每一条最短路径中，考虑加入一条最短的边，再从所有这些边中先选择最短的，这种策略即是Dijkstra算法。可以验证按长度顺序产生最短路径时，下一条最短路径总是由一条已产生的最短路径加上一条边形成。实际上，下一条最短路径总是由已产生的最短路径再扩充一条最短的边得到的，且这条路径所到达的顶点其最短路径还未产生。例如在图1310中，b中第二条路径是第一条路径扩充一条边形成的；第三条路径则是第二条路径扩充一条边；第四条路径是第一条路径扩充一条边；第五条路径是第三条路径扩充一条边。通过上述观察可用一种简便的方法来存储最短路径。可以利用数组p，pi给出从s到达i的路径中顶点i前面的那个顶点。在本例中p1501134。从s到顶点i的路径可反向创建。从i出发按pippipppi的顺序，直到到达顶点s或0。在本例中，如果从i5开始，则顶点序列为pi4p43p31s，因此路径为1345。为能方便地按长度递增的顺序产生最短路径，定义di为在已产生的最短路径中加入一条最短边的长度，从而使得扩充的路径到达顶点i。最初，仅有从s到s的一条长度为0的路径，这时对于每个顶点i，di等于asi（a是有向图的长度邻接矩阵）。为产生下一条路径，需要选择还未产生最短路径的下一个节点，在这些节点中d值最小的即为下一r