最短路径问题—Dijkstra算法

算法：

import java.util.*;public class Main6 {
         public static int N = 1050;
         public static final int INF = 0x3f3f3f3f;
         public static int [][]cost =new int[N][N];
         public static int dis[]=new int[N];
         public static boolean vis[]=new boolean[N];
         public static int n,m,s,t;
         public static int u,v,w;     public static void djc(int s){
         for(int i=1;i<=n;i++){
             dis[i]=INF;
             vis[i]=false;
         }
         dis[s]=0;
         vis[s]=true;
         for(int i=2;i<=n;i++){
             int Min = INF;
             for(int j=1;j<=n;j++){
                 if(!vis[j]&&dis[j]<Min)
                     Min= dis[j];
             }
         }
         vis[s]=true;
         for(int j=1;j<=n;j++){
             if(!vis[j]&&dis[s]+cost[s][j]<dis[j])
                 dis[j]=dis[s]+cost[s][j];
         }
     }    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            n = sc.nextInt();
            m = sc.nextInt();
            s = sc.nextInt();
            t = sc.nextInt();
            if(n==0&&m==0)
                System.exit(0);
            for(int i=0;i<N;i++){
                for(int j=0;j<N;j++)
                    cost[i][j]=INF;
            }
            for(int i=0;i<m;i++){
                u = sc.nextInt();
                v = sc.nextInt();
                w = sc.nextInt();
                cost[u][v]=cost[v][u]=w;
            }
            djc(s);
            System.out.println(dis[t]);
        }
}
}