最短路径 dijkstra

java

Description
目前网络上电子地图的使用很普遍。利用电子地图可以很方便地确定从一个地点到另一个地点的路径。特别地，可确定在城市中的公交换乘路线。
电子地图可以看成是一个图，而公交线路图可看成是带权有向图G =(V,E)，其中每条边的权是非负实数。
最短路径问题：计算从给定的起点s到另一个顶点t的最短路径的长度。
你的任务：对给定的一个（无向）图G，及G中的两点s、t，计算从起点s到顶点t的最短距离。
Input
输入文件中有若干组测试数据（组数不超过20）。
每组测试数据的第1行是一个正整数n，表示地图G的顶点数，n<50。
接下来的n行采用邻接矩阵方式描述这一个地图，第i行有n个数，依次表示第i个顶点与第1、2、3、…、n个顶点的路径长。假如两个顶点间无边相连，用一个-1表示。相邻的两个整数之间用空格隔开。注意，图中每个顶点 i处都没有自己到自己的边。
再在下面的一行上给出两个整数s、t，表示上述地图上的两个顶点。
每组测试数据之间有一空行。
输入直到文件结束。
Output
对输入中的每个城市地图，先在一行上输出“Case #”，其中“#”是测试数据的组号（从1开始），再在下一行输出从顶点s到顶点t的最短距离。
Sample Input
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
Sample Output
Case 1
5
Case 2
60

C++实现

#include<iostream>
#include<math.h>
#include<vector>
#include<memory.h>
using namespace std;
#define inf 1e9+7
const int N = 55;
int G[N][N];
int dis[N];
bool book[N];
int main(){
    int n;
    int tcase=0;
    while(cin >> n){
        for(int i=0; i<N; i++){
            memset(G[i],0,sizeof(G[i]));
        }
        for(int i=0;i<n;i++){
            for(int j=0; j<n; j++){
                cin >> G[i][j];
                if(G[i][j] == -1){
                    G[i][j] = i==j?0:inf;
                }
            }
        }
        int s,t;
        cin >> s >> t;
        s--;t--;
        memset(dis,0,sizeof(dis));
        memset(book,0,sizeof(book));
        for(int i=0; i<n; i++){
            dis[i] = G[s][i];
        }
        book[s] = true;
        int u=0;
        for(int i=0; i<n; i++){
            //找到当前最短路
            int min = inf;
            for(int j=0; j<n; j++){
                if(!book[j] && dis[j]<min){
                    min = dis[j];
                    u = j;
                }
            }
            book[u] = true;
            //更新最短路
            for(int v=0; v<n; v++){
                if(G[u][v]<inf){
                    if(dis[u]+G[u][v] < dis[v]){
                        dis[v] = dis[u]+G[u][v];
                    }
                }
            }
        }
        cout << "Case " << ++tcase << endl;
        cout << dis[t] << endl;
    }
}