一道图论问题.

题目

一道图论问题.
某公司在六个城市C1,C2,…,C6中都有分公司,从Ci到Cj的直接航程票价由下述矩阵的第(i,j)元素给出(∞表示无直接航路)：
0 50 ∞ 40 25 10
50 0 15 20 ∞ 25
∞ 15 0 10 20 ∞
40 20 10 0 10 25
25 ∞ 20 10 0 55
10 25 ∞ 25 55 0
该公司想算出一张任意两个城市之间的最廉航价路线表.试作出这样的表来.

答案

用Floyd算法求出各点到其他点的最短路径长度即可
矩阵如下
0 35 45 35 25 10
35 0 15 20 35 25
45 15 0 10 20 35
35 20 10 0 10 25
25 35 20 10 0 35
10 25 35 25 35 0
接下来会了吧.