dijkstra算法实现最短路径

算法原理

• 把所有点分成两组，A组是已经访问过的，B组是没有访问过的
• 从B组中找到离起点（下面统称为o点）最近的点 记为K点，并且将K移到A中
• 遍历剩余的B中的各个点，如果B中点m到o的距离大于o到k与k到m的距离和，则把o到m的最短距离设为后两者相加，否则不变
• 重复第二步第三步 直到所有的点都到A中

JAVA代码实现

public class Dijkatra {
    //寻路算法
    int[][] distances = {{0, 1, 2, 1000},
            {1, 0, 10000, 4},
            {2, 10000, 0, 1},
            {10000, 4, 1, 0}};
    char[] nodes = {'a','b','c','d'};
    String director = "-->";
    private int start = 0;
    private int end;

    public void getPathInfo() {
        int n = distances.length;//顶点个数
        float[] shortPath = new float[n];//记录start点到各个点的最短距离
        String[] path = new String[n];//记录start点到各个点的最短路径
//初始化
        for (int i = 0; i < n; i++) {
            path[i] = nodes[start] + director + nodes[i];
            shortPath[i] = distances[start][i];
        }
        boolean visited[] = new boolean[n];//是否已经求出
        shortPath[start] = 0;
        visited[start] = true;
        for (int i = 1; i < n; i++)//有N-1个点
        {
            int k = -1;//到i点最近得点
            float dimn = Float.MAX_VALUE;
            for (int j = 0; j < n; j++) {
                if (!visited[j] && shortPath[j] < dimn) {
                    dimn = shortPath[j];
                    k = j;
                }
            }
            visited[k] = true;
            //以k为中点访问隔各点
            for (int m = 0; m < n; m++) {
                //如果小于直接到它得距离，就改变shortPath以及path数组
                if (!visited[m] && dimn + distances[k][m] < shortPath[m]) {
                    shortPath[m] = dimn + distances[k][m];
                    path[m] = path[k] + director + nodes[m];
                }
            }
//如果找到了终点，就退出
            if (k == end) {
                break;
            }
        }
//打印最短距离
        System.out.println(nodes[start] + " " + nodes[end] + "最短距离 " + shortPath[end]);
//打印最短路线
        System.out.println(nodes[start] + " " + nodes[end] + "最短路线 " + path[end]);