dijkstra算法的作用(dijkstra算法步骤例题表格)

Dijkstra算法，中文翻译为离散算法，加权有向图g=(v，w ) ) v是节点的集合，w是边上权重值的集合，在集合w中，不直接连接的节点之间的距离表示为无限大)中该算法的中心思想是将图中的所有节点分为两个集合，集合s包括找到最短路径的节点，集合u包括到没有找到最短路径的节点的距离(初始值都设定为无限大)。从某一点v开始用宽度优先扫描思想扫描图表，每次发现节点的最短路径时，从集合u中删除该节点，添加到集合s中直到最后的u成为空集合。 s包含从图表中的所有节点到出发点的最小距离。添加过程中，从源点v到s的每个顶点的最短路径长度不会大于从源点v到u的任何顶点的最短路径长度。

Dijkstra算法流程：

选择某节点v作为出发点，如果从出发点到出发点的距离为0，则找到最小路径。从集合u中删除这个出发点并添加到集合s中。

在集合w中观察从出发点v到集合u的各节点的距离。找到距离最小的节点k (找到到k的最短路径)，从集合u中删除k并添加到集合s中。

以k为中间点，观察w中从k到u中节点m的距离，当w中m的值小于u中m的值(k与m直接相连)时，将w中m的值与k中k的值相加)从v经k到m的距离)和相加结果从w中v到m的值)

找出u中值最小的节点n，其值是从v到n的最短路径。从集合u中删除n并将其添加到集合s中。以n为中间点重复步骤3、4，直到u的所有节点移动到s为止。

图1

Dijkstra算法的手算方法

如图1所示，从节点a开始。首先，创建一个记录每个运算值的表。此表的标题表示集合u中包含的节点。未找到最短路径节点。 a、b、c、d )。第2行将各节点的距离初始化为无限大，用INF表示。

国际足联

点a是出发点，从自身到自身的路径最短，为0。即，找到了从a到a的最短路径。在a列的第二行中输入0，用下划线表示。这表示a已从u中删除。在表的第二行的最左边写a，表示将a添加到集合s中。

国际足联

创建表的第三行。此时集合u中含有{B、c、D}，从图中可以看出，A-B的距离为1 (查询集合w )，更新b列的数值并写入第3行。从图中可以看到，A-C的距离为5，更新b列的数值，写入第3行。从图中可以看出，A-D是不可直行的，标记为INF。在表的第3行中，对集合u中的要素{ 1，5，INF}求出最小值，得到b。此时，b列的第3行的数据为A-B的最小路径。为b列中的第三行数据加下划线，表示b将从集合u移动。同时在第三行的左端写b，在集合s中添加b。

国际足联

创建表的第四行。此时，集合u中包含{C，D}，节点b为中间点。从图中可以看出，B-C的距离为1，但A-B的距离保存在表b列中，如果为1，则A-B-C的距离为1=2。根据表c列的第3行的数据可知，当前到达c的距离为5(a直接到达c )。更新求出两个路径最小值min (5，1 )1)=2的c列数据，在c列的第4行写入2。由图可知，如果设B-D点的距离为1，则A-B-D的距离为1=2，但A-D不能直接到达，因此值取无限大INF。 (该值被记录在集合w中，在这种情况下，该值与表中的d列的数据相同。求出两个路径的最小值min(INF，1 )1)=2。更新行d列中的数据，并将2写入d列第4行。如果对集合u中的数据取最小值，则c和d都是2，如果选择其中一个，则计算从该节点到a的最短距离。例如选择c。在c上做标记。

国际足联

重复上述操作，创建表的第五行。此时，集合u中只包含{D}，节点c是中间点。从图中可以看出，C-D的距离是1。另一方面，A-C的最短距离已经求出，上表的c列的第4行为2 (经由节点b )。因此，A-B-C-D的距离为2 1=3。表中第d列第4行的记录到达d点的最小路径为2 (通过b点)，求出两条路径的最小值min (2，2 )1)=2。也就是说，d点的最小路径为2，将2写入d列第5行，标记d列第5行。此时，集合u为空集合，集合s中的要素为{A、b、c、D}，已经计算完毕。表的第五行中记录的数据是从a点到各点的最小路径值。

国际足联

具体的路径(经由的节点)可以通过回溯法求出。在最后一个表中找到有要求点的列，从下而上追溯，当值发生变化时，跳转到与该行对应的s集合中有要素的列，记录该点，追溯到到达出发点。

求出到达c点的具体路径，从c列第5行至上溯到第3行时值发生变化，第3行对应于s集合中的b，从b列第3行至上溯到b列第2行，值发生变化，与第2行对应的集合s中的要素以a为起点，后退完成具体路径是A-B-C。

与这一想法对应的C#源代码请参考《Dijkstra算法C#演示程序》。