算法题5 Dijkstra算法(最短距离)

发布时间: 2017年6月19日 00:23   时间限制: 1000ms   内存限制: 128M

目前网络上电子地图的使用很普遍。利用电子地图可以很方便地确定从一个地点到另一个地点的路径。特别地,可确定在城市中的公交换乘路线。

电子地图可以看成是一个图,而公交线路图可看成是带权有向图G =(V,E),其中每条边的权是非负实数。

最短路径问题:计算从给定的起点s到另一个顶点t的最短路径的长度。

 

你的任务:对给定的一个(无向)图G,及G中的两点s、t,计算从起点s到顶点t的最短距离。

输入文件中有若干组测试数据(组数不超过20)。

每组测试数据的第1行是一个正整数n,表示地图G的顶点数,n<50。

接下来的n行采用邻接矩阵方式描述这一个地图,第i行有n个数,依次表示第i个顶点与第1、2、3、…、n个顶点的路径长。假如两个顶点间无边相连,用一个-1表示。相邻的两个整数之间用空格隔开。注意,图中每个顶点 i处都没有自己到自己的边。

再在下面的一行上给出两个整数s、t,表示上述地图上的两个顶点。

每组测试数据之间有一空行。

输入直到文件结束。

对输入中的每个城市地图,先在一行上输出“Case #”,其中“#”是测试数据的组号(从1开始),再在下一行输出从顶点s到顶点t的最短距离。

复制
4
-1 2 -1 4
2 -1 3 -1
-1 3 -1 2
4 -1 2 -1
1 3

5
-1 10  -1 30 100
-1 -1 50 -1  -1
-1 -1 -1 -1 10
-1 -1 20 -1 60
-1 -1 -1 -1 -1
1 5
Case 1
5
Case 2
60
1615

old_judge

算法