利用E. Dijkstra发明的贪婪算法可以解决最短路径问题，它通过分步方法求出最短路径。每一步产生一个到达新的目的顶点的最短路径。下一步所能达到的目的顶点通过如下贪婪准则选取：在还未产生最短路径的顶点中，选择路径长度最短的目的顶点。也就是说， D i j k s t r a的方法按路径长度顺序产生最短路径。

　　首先最初产生从s 到它自身的路径，这条路径没有边，其长度为0。在贪婪算法的每一步中，产生下一个最短路径。一种方法是在目前已产生的最短路径中加入一条可行的最短的边，结果产生的新路径是原先产生的最短路径加上一条边。这种策略并不总是起作用。另一种方法是在目前产生的每一条最短路径中，考虑加入一条最短的边，再从所有这些边中先选择最短的，这种策略即是D i j k s t r a算法。

　　可以验证按长度顺序产生最短路径时，下一条最短路径总是由一条已产生的最短路径加上一条边形成。实际上，下一条最短路径总是由已产生的最短路径再扩充一条最短的边得到的，且这条路径所到达的顶点其最短路径还未产生。例如在图1 3 - 1 0中，b 中第二条路径是第一条路径扩充一条边形成的；第三条路径则是第二条路径扩充一条边；第四条路径是第一条路径扩充一条边；第五条路径是第三条路径扩充一条边。

　　通过上述观察可用一种简便的方法来存储最短路径。可以利用数组p，p [ i ]给出从s 到达i的路径中顶点i 前面的那个顶点。在本例中p [ 1 : 5 ] = [ 0 , 1 , 1 , 3 , 4 ]。从s 到顶点i 的路径可反向创建。从i 出发按p[i],p[p[i]],p[p[p[i]]], .的顺序，直到到达顶点s 或0。在本例中，如果从i = 5开始，则顶点序列为p[i]=4, p[4]=3, p[3]=1=s，因此路径为1 , 3 , 4 , 5。

　　为能方便地按长度递增的顺序产生最短路径，定义d [ i ]为在已产生的最短路径中加入一条最短边的长度，从而使得扩充的路径到达顶点i。最初，仅有从s 到s 的一条长度为0的路径，这时对于每个顶点i，d [ i ]等于a [ s ] [ i ]（a 是有向图的长度邻接矩阵）。为产生下一条路径，需要选择还未产生最短路径的下一个节点，在这些节点中d值最小的即为下一条路径的终点。当获得一条新的最短路径后，由于新的最短路径可能会产生更小的d值，因此有些顶点的d值可能会发生变化。