使用迪杰斯特拉算法解决带权图的最短路径问题

本文介绍使用迪杰斯特拉算法解决带权图的最短路径问题。如下图所示,计算从定点A到定点G的权值的最小路径。

image.png

迪杰斯特拉算法,英文是Dijkstra,是著名的单源最短路径算法。那它是如何寻找图中顶点的最短路径呢?这个算法的本质,是不断刷新起点与其他各个顶点之间的 “距离表”。

以下为迪杰斯特拉的详细过程:

第1步,创建距离表。表中的Key是顶点名称,Value是从起点A到对应顶点的已知最短距离。但是,一开始我们并不知道A到其他顶点的最短距离是多少,Value默认是无限大:

image.png

第2步,遍历起点A,找到起点A的邻接顶点B和C。从A到B的距离是5,从A到C的距离是2。把这一信息刷新到距离表当中:

image.png

第3步,从距离表中找到从A出发距离最短的点,也就是顶点C。

第4步,遍历顶点C,找到顶点C的邻接顶点D和F(A已经遍历过,不需要考虑)。从C到D的距离是6,所以A到D的距离是2+6=8;从C到F的距离是8,所以从A到F的距离是2+8=10。把这一信息刷新到表中:

image.png

接下来重复第3步、第4步所做的操作。

第5步,也就是第3步的重复,从距离表中找到从A出发距离最短的点(C已经遍历过,不需要考虑),也就是顶点B。

第6步,也就是第4步的重复,遍历顶点B,找到顶点B的邻接顶点D和E(A已经遍历过,不需要考虑)。从B到D的距离是1,所以A到D的距离是5+1=6,小于距离表中的8;从B到E的距离是6,所以从A到E的距离是5+6=11。把这一信息刷新到表中:

image.png

(在第6步,A到D的距离从8刷新到6,可以看出距离表所发挥的作用。距离表通过迭代刷新,用新路径长度取代旧路径长度,最终可以得到从起点到其他顶点的最短距离)

第7步,从距离表中找到从A出发距离最短的点(B和C不用考虑),也就是顶点D。

第8步,遍历顶点D,找到顶点D的邻接顶点E和F。从D到E的距离是1,所以A到E的距离是6+1=7,小于距离表中的11;从D到F的距离是2,所以从A到F的距离是6+2=8,小于距离表中的10。把这一信息刷新到表中:

image.png

第9步,从距离表中找到从A出发距离最短的点,也就是顶点E。

第10步,遍历顶点E,找到顶点E的邻接顶点G。从E到G的距离是7,所以A到G的距离是7+7=14。把这一信息刷新到表中:

image.png

第11步,从距离表中找到从A出发距离最短的点,也就是顶点F。

第12步,遍历顶点F,找到顶点F的邻接顶点G。从F到G的距离是3,所以A到G的距离是8+3=11,小于距离表中的14。把这一信息刷新到表中:

image.png

就这样,除终点以外的全部顶点都已经遍历完毕,距离表中存储的是从起点A到所有顶点的最短距离。显然,从A到G的最短距离是11。(路径:A-B-D-F-G)

按照上面的思路,我们来看一下代码实现:

/**
 * Dijkstra最短路径算法
 * @param graph
 * @param startIndex
 * @return
 */
public static Map<Integer,Integer> dijkstra(Graph graph,int startIndex){
    //创建距离表,存储从起点到每一个定点的临时距离;
    Map<Integer,Integer> distanceMap=new HashMap<Integer,Integer>();
    //记录遍历过的定点;
    Set<Integer> accessedSet=new HashSet<Integer>();
    //图的定点数量;
    int size=graph.vertexs.length;
    //初始化最短路径表,到达每个定点的路径默认为无穷大;
    for(int i=1;i<size;i++){
        distanceMap.put(i, Integer.MAX_VALUE);
    }
    //遍历起点,刷新距离表;
    accessedSet.add(0);
    List<Edge> edgesFromStart=graph.adj[startIndex];
    for(Edge edge:edgesFromStart){
        distanceMap.put(edge.index, edge.weight);
    }
    //主循环,重复[遍历最短距离顶点和刷新距离表]的操作;
    for(int i=1;i<size;i++){
        //寻找最短距离顶点;
        int minDistanceFromStart=Integer.MAX_VALUE;
        int minDistanceIndex=-1;
        for(int j=1;j<size;j++){
            if(!accessedSet.contains(j) && distanceMap.get(j)<minDistanceFromStart){
                minDistanceFromStart=distanceMap.get(j);
                minDistanceIndex=j;
            }
        }
        if(minDistanceIndex==-1){
            break;
        }
        //遍历顶点,刷新距离表;
        accessedSet.add(minDistanceIndex);
        for(Edge edge : graph.adj[minDistanceIndex]){
            if(accessedSet.contains(edge.index)){
                continue;
            }
            int weight=edge.weight;
            int preDistance=distanceMap.get(edge.index);
            if(weight!=Integer.MAX_VALUE && (minDistanceFromStart+weight<preDistance)){
                distanceMap.put(edge.index, minDistanceFromStart+weight);
            }
        }
    }
    return distanceMap;
}
public static void main(String[] args){
    Graph graph=new Graph(7);
    initGraph(graph);
    Map<Integer,Integer> distanceMap=dijkstra(graph,0);
    int distance=distanceMap.get(6);
    System.out.println(distance);
}
private static void initGraph(Graph graph){
    graph.vertexs[0]=new Vertex("A");
    graph.vertexs[1]=new Vertex("B");
    graph.vertexs[2]=new Vertex("C");
    graph.vertexs[3]=new Vertex("D");
    graph.vertexs[4]=new Vertex("E");
    graph.vertexs[5]=new Vertex("F");
    graph.vertexs[6]=new Vertex("G");
    graph.adj[0].add(new Edge(1,5));
    graph.adj[0].add(new Edge(2,2));
    graph.adj[1].add(new Edge(0,5));
    graph.adj[1].add(new Edge(3,1));
    graph.adj[1].add(new Edge(4,6));
    graph.adj[2].add(new Edge(0,2));
    graph.adj[2].add(new Edge(3,6));
    graph.adj[2].add(new Edge(5,8));
    graph.adj[3].add(new Edge(1,1));
    graph.adj[3].add(new Edge(2,6));
    graph.adj[3].add(new Edge(4,1));
    graph.adj[3].add(new Edge(5,2));
    graph.adj[4].add(new Edge(1,6));
    graph.adj[4].add(new Edge(3,1));
    graph.adj[4].add(new Edge(6,7));
    graph.adj[5].add(new Edge(2,8));
    graph.adj[5].add(new Edge(3,2));
    graph.adj[5].add(new Edge(6,3));
    graph.adj[6].add(new Edge(4,7));
    graph.adj[6].add(new Edge(5,3));
}
/**
 * 图的顶点
 * @author itpro
 *
 */
private static class Vertex{
    String data;
    Vertex(String data){
        this.data=data;
    }
}
/**
 * 图的边
 * @author itpro
 *
 */
private static class Edge{
    int index;
    int weight;
    Edge(int index,int weight){
        this.index=index;
        this.weight=weight;
    }
}
/**
 * 图
 * @author itpro
 *
 */
private static class Graph{
    private Vertex[] vertexs;
    private LinkedList<Edge> adj[];
    Graph(int size){
        //初始化定点和邻接矩阵
        vertexs=new Vertex[size];
        adj=new LinkedList[size];
        for(int i=0;i<adj.length;i++){
            adj[i]=new LinkedList<Edge>();
        }
    }
}