20. (计算题) 在下面的有向图中应用Dijkstra算法计算顶点1到其他各个顶点的最短路径的长度。(要求:用图表法给出详细的求解过程)
时间: 2024-04-01 19:37:15 浏览: 27
下面是该有向图的邻接矩阵表示:
| | 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到该顶点的最短路径长度。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_lunwen.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)