迪杰斯特拉算法之解决单源最短路径问题

迪杰斯特拉算法

迪杰斯特拉(Dijkstra)算法是典型**最短路径算法**，用于计算一个结点到其它结点的最短路径。它的主要特点是以起始点为中心向外扩展(利用广度优先搜索思想)，直到扩展到终点。

迪杰斯特拉(Dijkstra)算法最佳应用-最短路径

1. 战争时期，胜利乡有7个村庄(A,B,C,D,E,F,G),现在又六个邮差，从G点出发，需要分别把邮件送到A,B,C,D,E,F六个村庄
2. 各个村庄的距离用边线表示(权)，比如A-B距离5公里
3. 问：如何计算出G村庄到其它各个村庄的最短距离？

• 思路分析
  • 从G开始，初始化三个数组：final[]表示该顶点是否已经访问过；dist[]表示G点到其它各点之间的最短路径长度;path[]表示路径上的前驱
  • 从G点(下标为6)开始，令其final[6]=true,dist[6]=0,path[6]=-1；其余顶点final[k]=false,disk[k]=arcs[6][k],path[k]=(arcs[6][k]==特定值) ? -1:6（其中arcs[u][v]代表从u顶点到v顶点的边线，这里用特定值表示不存在G顶点到某一顶点的路径）
  • n-1轮处理：循环遍历所有顶点，找到还没确定最短路径，且dist最小的顶点vi，令final[i]=true。并检查所有邻接自vi的顶点vj，如果final[j]=false并且dist[i]+arcs[i][j]<dist[j]，则令其dist[j]=dist[i]+arcs[i][j],path[j]=i
• 代码实现

import java.util.Arrays;

public class DijkstraDemo {
    private static final int INF = Integer.MAX_VALUE;
    public static void main(String[] args) {
        char[] vertexes = {'A','B','C','D','E','F','G'};
        int[][] matrix = {
                {0,5,7,INF,INF,INF,2},
                {5,0,INF,9,INF,INF,3},
                {7,INF,0,INF,8,INF,INF},
                {INF,9,INF,0,INF,4,INF},
                {INF,INF,8,INF,0,5,4},
                {INF,INF,INF,4,5,0,6},
                {2,3,INF,INF,4,6,0}
        };
        Graph graph = new Graph(vertexes, matrix);
        Dijkstra dijkstra = new Dijkstra(vertexes.length);
        dijkstra.dijkstra(graph, 6);
        dijkstra.show(vertexes);
    }
}
class Dijkstra {
    // 是否找到最短路径
    private boolean[] finalArr;
    // 从某一个顶点出发到其它顶点的最短路径
    private int[] dist;
    // 找前驱，如果-1表示没有前驱
    private final int[] path;
    private static final int INF = Integer.MAX_VALUE;

    /**
     * @param vertexNum
     */
    public Dijkstra(int vertexNum) {
       finalArr = new boolean[vertexNum];
       dist = new int[vertexNum];
       // 用最大值表示没有路径
        Arrays.fill(dist,INF);
        path = new int[vertexNum];
        Arrays.fill(path,-1);
    }

    /**
     * 迪杰斯特拉算法
     * @param graph 图相关数据
     * @param start 从哪一个顶点开始
     */
    public void dijkstra(Graph graph,int start) {
        // 对初始顶点进行初始化
        finalArr[start] = true;
        dist[start] = 0;
        path[start] = -1;

        char[] vertexes = graph.getVertexes();
        int[][] edges = graph.getEdges();
        int length = vertexes.length;
        // 初始化除初始顶点之外的其它顶点
        for (int i = 0; i < length; i++) {
            if (start != i) {
                dist[i] = edges[start][i];
                path[i] = dist[i] == INF?-1:start;
            }
        }
        // 进行n-1论循环
        for (int i = 0; i < length - 1; i++) {
            // 每次挑选出没有确定最短路径的顶点之后更新顶点集的最短距离
            int min = INF;
            int minIndex = -1;
            for (int j = 0; j < length; j++) {
                if (!finalArr[j] && dist[j] < min) {
                    min = dist[j];
                    minIndex = j;
                }
            }
            // 确定最小路径
            finalArr[minIndex] = true;
            // 确定是否存在到其它未确定最短路径的顶点
            for (int j = 0; j < length; j++) {
                if (!finalArr[j] && edges[minIndex][j] != INF && (dist[minIndex] + edges[minIndex][j] < dist[j])) {
                    dist[j] = dist[minIndex] + edges[minIndex][j];
                    path[j] = minIndex;
                }
            }
        }

    }

    public void show(char[] vertexes) {
        int len = vertexes.length;
        for(int i = 0; i < len;i++) {
            System.out.println("到顶点" + vertexes[i] + "的最短路径为" + dist[i]);

            int p = path[i];
            System.out.print("存在的路径是：");
            System.out.print(vertexes[i] + "<-");
            while(p != -1) {
                System.out.print(vertexes[p] + "<-");
                p = path[p];
            }
            System.out.println();
        }
    }
}
class Graph {
    // 顶点集
    private char[] vertexes;
    // 邻接矩阵
    private int[][] edges;

    public Graph(char[] vertexes, int[][] edges) {
        int length = vertexes.length;
        this.vertexes = new char[length];
        this.edges = new int[length][length];
        // 初始化顶点集和邻接矩阵
        for (int i = 0; i < length; i++) {
            this.vertexes[i] = vertexes[i];
        }
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < length; j++) {
                this.edges[i][j] = edges[i][j];
            }
        }
    }

    public char[] getVertexes() {
        return vertexes;
    }

    public int[][] getEdges() {
        return edges;
    }
}