题目：从节点N到节点1的求最短路径。

分析：这道题陷阱比较多，首先是输入的数据，第一个是表示路径条数，第二个是表示节点数量，在 这里WA了四次。再有就是多重边，要取最小值。最后就是路径的长度的最大值不是100，而是100001。用Dijkstra求最短路径，感觉 Dijkstra和Prim很像，都是从结点中找到路径最小的一条，然后再做某种更新。Dijkstra是看看源节点通过当前节点能否缩短从源头到其他节 点的路径，而Prim则是通过加入当前节点到生成树，然后更新生成树中的路径数量，再从中找到最小路径。

package Map;

import java.util.Scanner;

/**

 * Dijkstra最短路径

 */

public class Poj_2387_Dijkstra {

        static int n, m;

        static int MAXV = 2010;

        static int MAX = 100001;

        static int map[][] = new int[MAXV][MAXV];

        static boolean vis[] = new boolean[MAXV];

        public static int dijksrta(int V) {

                vis[V] = true;

                for (int i = 1; i <= n; i++) {

                        int min = MAX;

                        int k = 0;

                        for (int j = 1; j <= n; j++) {

                                if (!vis[j] && map[V][j] < min) {

                                        min = map[V][j];

                                        k = j;

                                }

                        }

                        vis[k] = true;

                        for (int j = 1; j <= n; j++) {

                                if (!vis[j] && min + map[k][j] < map[V][j]) {

                                        map[V][j] = min + map[k][j];

                                }

                        }

                }

                return map[V][1];

        }

        public static void main(String args[]) {

                Scanner sc = new Scanner(System.in);

                m = sc.nextInt();

                n = sc.nextInt();

                for (int i = 1; i <= n; i++) {

                        for (int j = 1; j <= n; j++) {

                                map[i][j] = MAX;

                        }

                        map[i][i] = 0;

                }

                for (int i = 1; i <= m; i++) {

                        int s = sc.nextInt();

                        int e = sc.nextInt();

                        int val = sc.nextInt();

                        if(map[s][e] > val){   //重边问题，去最小的

                                map[s][e] = val;

                                map[e][s] = val;

                        }

                }

                System.out.println(dijksrta(n));

        }

}

版权声明：本文为博主原创文章，未经博主允许不得转载。