Dijkstra算法(以下称为迪杰斯特拉算法)是非常常用的解决单源(指只有一个起点)赋权(指边均带有权值, 而且是非负权值)图的最短路径问题的算法，本文我希望由浅入深的解析该算法具体是怎么玩的。

使用Dijkstra算法确定最短路径

首先，来个热身，我们实战一下。

迪杰斯特拉算法仅适用于带权图，这里我随意画了一张有向带权图：

该图中，我们设定A是起点，H是终点。如何找到通往H的代价最小的路径呢？

迪杰斯特拉算法的思想是以广度优先搜索的方式遍历图，一步一个脚印，每步确定一次最短路径，直到遍历完整个图，就确定了所有的最短路径。这么说可能有点抽象，下面直接通过实践方式，以上图为实例讲解迪杰斯特拉算法的流程。

(1) 第一轮

首先，我们从起始点A出发，得到可以走一步到达的路径，分别为A->B，A->C和A->D。此时我们很容易发现其中的最短路径为A->C，权值仅为3。

我们将获得的最短路的终点C称为确定点，因为它的最短路径已经被确定。同时，起始点A也是一个确定点，因为它的最短路就是它自身。下文我们将会把确定点标红。

显然第一步非常简单，但为了便于记录，接下来我们不会这样做。

实际上我们需要列出一个表格，如下表所示：

其中，行头是顶点名，列头N={1， 2， 3， ... }代表走过的步数。对应的单元格是经过N步所得到的路径以及权值。

表中标为红色的顶点代表该点是确定点，标为红色的单元格代表该路径已确定是最短路径，未标红的，则其最短路径还未确定。

在下文中我们需要通过该表格来确定新的最短路径，具体的方式是：该轮中权值最小的路径为新的最短路径。

类似地，我们将图更新为下图所示的形式。

(2) 第二轮

每轮开始我们选择上一轮获得的最短路径的终点作为下一步的起始点，比如此处我们需要选择点C作为这一轮的起始点。然后进行一轮遍历，获得新的路径，并写入到表格中。

此处C只能到达E，则到E的路径为A->C->E，我们将这个结果写入到表格的第二列中，代表这是第二轮的结果，并把之前的结果照写。

观察表格，我们发现第二列中，A->D的权值最小，我们此时优先把A->D标为确定点。

(3) 第三轮

从上一轮的确定点D出发，我们得到A->D->C和A->D->F这两条路径。由于C的最短路已被确定，所以我们不会更新C的最短路径，而由于暂时没有到达F的路径，于是我们需要将A->D->F加入到表格中。

此时我们同时也确定了A->C->E为新的最短路。

(4) 第四轮

按上文中的方法，我们继续更新表格。

此时因为A->C->E->F的权值12小于A->D->F的权值17，所以我们将A->D->F这条路径舍弃了，用新的权值更小的路径代替。

观察第四列，我们发现A->B和A->C->E->F的权值是一样的，其实这时候选择谁作为新的最短路都可以，但是依据先来后到的原则，我们选择第一个作为最短路，并把B标为确定点。

(5) 第五轮

本轮中只有一条路径A->B->E，但是E的最短路已经被确定，所以这条新的路径被直接舍弃了。

接着我们直接选择新的确定点为F。

结果

由于过程较为重复，此处我们一口气将结果写出来。

在表格第七列中，我们获得了从A点出发到达所有其他顶点的最短路径。

此外，仔细观察全部标红的图，我们将非最短路的边去除。

我们便构成了一个极小联通子图，它的任意一条通路都是最短路径。同时，我们获得了通往H的最短路A->C->E->H。