最短路径问题

废话少说，先来一道题目

http://acm.hdu.edu.cn/showproblem.php?pid=2544

读题后抽象一下也就是说N是顶点M是边

然后题目要求我们求出顶点1到顶点N的最短路径

先用floyd算法解决(这个算法简单易懂，三层for循环逐个遍历，找出所有点对点之间的最短路径)

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while(in.hasNext()) {
            final int MAX = Integer.MAX_VALUE;
            System.out.println(MAX);
            int n = in.nextInt();
            int m = in.nextInt();
            in.nextLine();
            if(n == m && n == 0) {
                break;
            }
            int[][] num = new int[n][n];
            for (int i = 0; i < n; i++) {
                for(int j = 0; j < n; j++) {
                    if(i == j) {
                        num[i][j] = 0;
                    }
                    num[i][j] = MAX;
                }
            }
            for(int i = 0; i < m; i++) {
                int tempi = in.nextInt();
                int tempj = in.nextInt();
                int tempv = in.nextInt();
                in.nextLine();
                if(tempv < num[tempi-1][tempj-1]) {
                    num[tempi-1][tempj-1] = tempv;
                    num[tempj-1][tempi-1] = tempv;
                }
            }
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    for (int k = 0; k < n; k++) {
                        if((num[i][k] + num[k][j]) < num[i][j]) {
                            num[i][j] = num[i][k] + num[k][j];
                            num[j][i] = num[i][k] + num[k][j];
                        }
                    }
                }
            }
            System.out.println(num[0][n-1]);
        }
    }
}

再来介绍一下狄杰斯特拉算法

这个算法是用来求某个顶点到其他顶点的最短路径

用到了贪心思想，就是说求最短路径，比如说有ABCD这四个点A->A=0，你要求出A->B,A->C,A->D的最短路径。那这个算法的思想是不考虑到具体某个点的最短路径，我先求出最短路径

，然后把到最短路径的点表示已经访问（visit[]数组就是用来标记这个的，visit[start]表示原点到原点一开始就设置为已经访问）这个时候next用来表示到哪个点有最短路径，我记录下来。

要注意的一点是min最小值是求剩下来的这些点的最小值，因此每次有一个点被标记已经访问后需要重新设置。

import java.util.*;

public class Main {
    public static void dijkstra(int start, int end, int n, int[][] num) {
        int next = start;//用来标记已经访问的点
        int[] dis = new int[n];//表示原点start到end的最近距离
        boolean[] visit = new boolean[n];
        visit[start] = true;//用来表示是否已经访问
        for (int i = 0; i < n; i++) {
            dis[i] = num[start][i];
        }
　　　　//初始化
        dis[start] = 0;
        for (int i = 0; i < n; i++) {
            int min = 0x3f3f3f3f;//最小值
            for (int j = 0; j < n; j++) {
                if (visit[j] == false && min > dis[j]) {//寻找剩下这些点中的最小值
                    min = dis[j];
                    next = j;
                }
            }
            visit[next] = true;
            for (int j = 0; j < n; j++) {
                if (visit[j] == false) {//更新dis[]数组
                    if (dis[j] > dis[next] + num[next][j]) {
                        dis[j] = dis[next] + num[next][j];
                    }
                }
            }
        }
        
        System.out.println(dis[end]);
        

    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            final int MAX = 0x3f3f3f3f;
            int n = in.nextInt();
            int m = in.nextInt();
            in.nextLine();
            if (n == m && n == 0) {
                break;
            }
            int[][] num = new int[n][n];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (i == j) {
                        num[i][j] = 0;    
                    }
                    else {
                        num[i][j] = MAX;
                        num[j][i] = MAX;
                    }
                }
            }
            for (int i = 0; i < m; i++) {
                int tempi = in.nextInt();
                int tempj = in.nextInt();
                int tempv = in.nextInt();
                in.nextLine();
                if (tempv < num[tempi - 1][tempj - 1]) {
                    num[tempi - 1][tempj - 1] = tempv;
                    num[tempj - 1][tempi - 1] = tempv;
                }
            }
            dijkstra(0, n - 1, n, num);
        }
    }
}