2.3.4 Dijkstra算法实现

通过上一节的图解，相信大家对单源最短路径Dijkstra算法已经有了了解，那么接下来我们进行实战编程。我们通过程序来找到到达老王家的最短路径，吃到丰盛的午餐。去老王家的路径如图2.14所示。算法完整代码如下。

Dijkstra算法程序运行结果如图2.26所示。

图2.26 Dijkstra算法程序运行结果

可以发现，程序的运行结果和表2.23的分析结果是一致的。我们已经成功地找到了到达老王家的最短路径，出发去吃午餐喽。接下来我们对程序重要的数据结构和方法进行讲解。

首先我们通过邻接矩阵表示图，邻接矩阵在Python中通过二维列表进行表示，二维列表的行号表示结点，每行的数据是一维列表，表示结点之间的距离，图2.17的邻接矩阵如下所示。

算法中我们定义三个列表，passed、nopass和dis分别存放的是已经确定最短距离的结点、还不确定最短距离的结点和最短距离。

通过贪心策略，找到最小距离的结点进行扩展：

最后是Dijkstra算法的核心，找到最新的结点以后，根据最新的结点更新其他未找到最短距离结点的距离，如下所示：