在右边的带权有向图，应用 Dijkstra 算法计算源顶点 1 到其他顶 点间的最短路劲的迭代过程填入

以下是源顶点为1的Dijkstra算法迭代过程：

| 迭代次数 | S | 1 | 2 | 3 | 4 | 5 |
| -------- | - | - | -------- | -------- | -------- | -------- |
| 0 | | 1 | $\infty$ | $\infty$ | $\infty$ | $\infty$ |
| 1 | 1 | | 6 | 3 | $\infty$ | $\infty$ |
| 2 | 1 | | 6 | 3 | 8 | 9 |
| 3 | 1 | | 6 | 3 | 8 | 7 |
| 4 | 1 | | 6 | 5 | 8 | 7 |
| 5 | 1 | | 6 | 5 | 8 | 7 |

解释：

- 第一行表示迭代次数和当前已在S中的顶点。
- 在第一次迭代中，从源点1出发，到达顶点2和3的距离为6和3，更新它们的最短距离。
- 在第二次迭代中，从S中选取距离最短的顶点3，更新它能到达的顶点4和5的最短距离。
- 后续迭代同理，直到所有顶点的最短距离都被确定。

相关问题

20. (计算题) 在下面的有向图中应用Dijkstra算法计算顶点1到其他各个顶点的最短路径的长度。（要求：用图表法给出详细的求解过程）

下面是该有向图的邻接矩阵表示：

| | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| 1 | 0 | 3 | 10| ∞ |
| 2 | ∞ | 0 | ∞ | 4 |
| 3 | ∞ | 2 | 0 | ∞ |
| 4 | 1 | ∞ | ∞ | 0 |

其中，∞表示两个顶点之间没有边相连。

Dijkstra算法的求解过程如下：

1. 初始化：

选定起始顶点为1，将其标记为已访问。对于与1直接相连的顶点2和3，更新其距离为从1到该顶点的距离，即d[2]=3，d[3]=10。

| | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| d | 0 | 3 | 10| ∞ |
| v | T | F | F | F |

2. 第一轮迭代：

对于未访问的顶点中，距离起点最近的是顶点2，将其标记为已访问。然后更新与2直接相连的顶点3和4的距离，即d[3]=5，d[4]=7。

| | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| d | 0 | 3 | 5 | 7 |
| v | T | T | F | F |

3. 第二轮迭代：

对于未访问的顶点中，距离起点最近的是顶点3，将其标记为已访问。然后更新与3直接相连的顶点4的距离，即d[4]=6。

| | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| d | 0 | 3 | 5 | 6 |
| v | T | T | T | F |

4. 第三轮迭代：

对于未访问的顶点中，距离起点最近的是顶点4，将其标记为已访问。此时，所有顶点均已访问，算法结束。

| | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| d | 0 | 3 | 5 | 6 |
| v | T | T | T | T |

因此，从顶点1到其他各个顶点的最短路径长度为：

d[1]=0，d[2]=3，d[3]=5，d[4]=6

下面是图表法的求解过程：

| 步骤 | 已访问的顶点 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 1 | 1 | 0 | 3 | 10| ∞ |
| 2 | 1,2 | 0 | 3 | 5 | 7 |
| 3 | 1,2,3 | 0 | 3 | 5 | 6 |
| 4 | 1,2,3,4 | 0 | 3 | 5 | 6 |

其中，第一行表示算法的初始化状态，第一列表示每一步算法结束时已访问的顶点，其他格子中的数字表示从顶点1到该顶点的最短路径长度。

有向图的dijkstra算法计算全部点的的最短路径，迭代次数是n次还是n-1次，请举例说明

Dijkstra算法计算有向图全部点的最短路径，迭代次数是n次。

举个例子，考虑下面这个有向图：

     2
A ------> B ------> D
|\        |\        |\
| \       | \       | \
|  1      |  3      |  1
|   \     |   \     |   \
|    \    |    \    |    \
|     \   |     \   |     \
|      \  |      \  |      \
|       \ |       \ |       \
v        vv        vv        v
C ------> E ------> F ------> G
     2      1      1       3

假设我们要求从顶点A到所有其他顶点的最短路径。我们可以用Dijkstra算法来解决这个问题。

首先，将A标记为已知最短路径顶点，将其路径长度设为0。然后，从A开始，依次考虑其相邻顶点B和C。由于B和C的路径长度分别为2和1，我们可以将它们标记为已知最短路径顶点，并将它们的路径长度设为2和1。接下来，我们考虑从B和C出发，到达它们各自的相邻顶点D和E。由于B-D的路径长度为3，C-E的路径长度为3，我们可以将D和E标记为已知最短路径顶点，并将它们的路径长度设为5和4。然后，我们考虑从D和E出发，到达它们各自的相邻顶点F。由于D-F的路径长度为1，E-F的路径长度为2，我们可以将F标记为已知最短路径顶点，并将其路径长度设为6。最后，我们考虑从F出发，到达它的相邻顶点G。由于F-G的路径长度为3，我们可以将G标记为已知最短路径顶点，并将其路径长度设为9。

在以上的计算过程中，我们可以发现，每次迭代时，Dijkstra算法都会将已知最短路径顶点的相邻顶点标记为候选最短路径顶点，并更新它们的路径长度。由于图中共有7个顶点，因此Dijkstra算法的迭代次数是7次，即n次。