考虑有向图 (1) 请写出上图的邻接矩阵 (2) 请用Floyd算法计算
时间: 2023-10-07 10:06:08 浏览: 86
(1) 上图的邻接矩阵表示如下:
| | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 1 | 0 | 2 | 6 | 4 | ∞ |
| 2 | ∞ | 0 | 3 | ∞ | ∞ |
| 3 | 7 | ∞ | 0 | 1 | 5 |
| 4 | ∞ | ∞ | 12| 0 | 8 |
| 5 | ∞ | ∞ | ∞ | ∞ | 0 |
其中,∞表示两个顶点之间没有边相连。
(2) 用Floyd算法计算该图的最短路径如下:
首先初始化距离矩阵D为邻接矩阵,然后按照以下公式进行迭代:
D[i][j] = min(D[i][j], D[i][k] + D[k][j])
其中,k表示当前正在处理的中间顶点,i和j表示要计算的两个顶点。迭代完成后,D[i][j]表示从顶点i到顶点j的最短路径长度。
具体求解过程如下:
1. 初始状态:
D =
| | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 1 | 0 | 2 | 6 | 4 | ∞ |
| 2 | ∞ | 0 | 3 | ∞ | ∞ |
| 3 | 7 | ∞ | 0 | 1 | 5 |
| 4 | ∞ | ∞ | 12| 0 | 8 |
| 5 | ∞ | ∞ | ∞ | ∞ | 0 |
2. 第一轮迭代:
选取中间顶点k=1,计算出D[2][4]=7,D[3][1]=7,D[3][4]=5,D[4][1]=11,D[4][2]=13,D[5][1]=∞,D[5][2]=∞,D[5][3]=∞,D[5][4]=∞。
D =
| | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 1 | 0 | 2 | 6 | 4 | ∞ |
| 2 | ∞ | 0 | 3 | 7 | ∞ |
| 3 | 7 | ∞ | 0 | 1 | 5 |
| 4 | 11| 13| 12| 0 | 8 |
| 5 | ∞ | ∞ | ∞ | ∞ | 0 |
3. 第二轮迭代:
选取中间顶点k=2,计算出D[1][3]=5,D[1][4]=9,D[1][5]=∞,D[3][4]=4,D[3][5]=8,D[5][1]=16,D[5][2]=18,D[5][3]=∞,D[5][4]=16。
D =
| | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 1 | 0 | 2 | 5 | 4 | 12|
| 2 | ∞ | 0 | 3 | 7 | 15|
| 3 | 7 | 9 | 0 | 1 | 5 |
| 4 | 11| 13| 12| 0 | 8 |
| 5 | 16| 18| 21| 16| 0 |
4. 第三轮迭代:
选取中间顶点k=3,计算出D[1][4]=5,D[1][5]=13,D[2][4]=8,D[2][5]=∞,D[4][5]=8。
D =
| | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 1 | 0 | 2 | 5 | 4 | 12|
| 2 | ∞ | 0 | 3 | 7 | 15|
| 3 | 7 | 9 | 0 | 1 | 5 |
| 4 | 5 | 7 | 6 | 0 | 8 |
| 5 | 13| 15| 14| 8 | 0 |
5. 第四轮迭代:
选取中间顶点k=4,计算出D[1][5]=12,D[2][5]=20,D[3][5]=5。
D =
| | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 1 | 0 | 2 | 5 | 4 | 12|
| 2 | ∞ | 0 | 3 | 7 | 15|
| 3 | 7 | 9 | 0 | 1 | 5 |
| 4 | 5 | 7 | 6 | 0 | 8 |
| 5 | 12| 14| 5 | 8 | 0 |
因此,从顶点i到顶点j的最短路径长度为:
d[1][2]=2,d[1][3]=5,d[1][4]=4,d[1][5]=12,
d[2][1]=∞,d[2][3]=3,d[2][4]=7,d[2][5]=15,
d[3][1]=7,d[3][2]=9,d