利用Dijkstra算法在下图中求出从源点V1到其余各点的最短路.
1.V1
|
|
V1 |
V2 |
V3 |
V4 |
V5 |
V6 |
| V1 |
|
40 |
30 |
20 |
10 |
|
2.过V5
|
|
V1 |
V2 |
V3 |
V4 |
V5 |
V6 |
| V1 |
0 |
40 |
30 |
20 |
10 |
|
| V1(V5) |
0 |
40 |
30 |
20 |
|
|
3
|
|
V1 |
V2 |
V3 |
V4 |
V5 |
V6 |
| V1 |
0 |
40 |
30 |
20 |
10 |
|
| V1(V5) |
0 |
40 |
30 |
20 |
|
|
| V1(v4,v5) |
0 |
35(4) |
26(4) |
|
|
|
4
|
|
V1 |
V2 |
V3 |
V4 |
V5 |
V6 |
| V1 |
0 |
40 |
30 |
20 |
10 |
- |
| V1(V5) |
0 |
40 |
30 |
20 |
|
- |
| V1(v4,v5) |
0 |
35(4) |
26(4) |
|
|
- |
| V1(v4,v5,v3) |
0 |
35(4) |
|
|
|
41(3) |
5
|
|
V1 |
V2 |
V3 |
V4 |
V5 |
V6 |
| V1 |
0 |
40 |
30 |
20 |
10 |
- |
| V1(V5) |
0 |
40 |
30 |
20 |
|
- |
| V1(v4,v5) |
0 |
35(4) |
26(4) |
|
|
- |
| V1(v4,v5,v3) |
0 |
35(4) |
|
|
|
41(3) |
| V1(v4,v5,v3,v2) |
0 |
|
|
|
|
41(3) |
即v1-v2: 1-4-2;
v1-v3: 1-4-3;
v1-v4: 1-4;
v1-v5: 1-5;
v1-v6: 1-4-3-6.