Wechat: yu389741| Email: gisdqy@163.com

Shop:https://www.giserdqy.com/shop

Dijkstra最短路径算法浅析及java实现



一直以来对于Dijkstra算法都是只知道其大致步骤,至于为什么该算法能保证找到的都是最短路径却一直似懂非懂。今天花费了半天功夫仔细思考了其中的原理,感觉有些收获。为了防止像之前一样一边捡一边丢,决定记录一下~~~

问题 :

G(V,E)为简单无向赋权连通图, V为其顶点集,E为其边集。邻接矩阵记为M, M(Vi,Vj)表示图中连接顶点ViVj的边的权值。求G中顶点P到其余各个顶点的最短路径。

准备知识:

  1. 如果P(i,j)=Vi...Vk...Vs...Vj是从顶点ij的最短路径,ks是这条路径上的一个中间顶点,那么P(k,s)必定是从ks的最短路径;
  2. 要表示从图G中的任一顶点R到顶点P的最短路径,只需记录图中每一个顶点R的前继顶点即可;

Dijkstra算法步骤:

符号说明

我搜到的大多数博客文章均把顶点集分成两个子集:已被选中的顶点集U和未被选中的顶点集V。我刚开始看得云里雾里的,看了E. W. DIJKSTRA 1959年的那篇文章才又明白了一些。在文章中顶点集实际上是被分为三个子集。符号说明如下:

  1. 集合A: 已被选中的顶点集合,即已经确定了到起始顶点P的最短路径的顶点集合;
  2. 集合B: 与A中至少一个顶点邻接且未被选中的顶点集合;
  3. 集合C: 未被选中且不与A中任何顶点邻接的顶点集合;
  4. D(Vi): 图G中任一顶点Vi到起始顶点P的距离;
  5. Pre(Vi): 顶点P到顶点Vi的最短路径中顶点Vi的前继顶点;

算法步骤

准备:计算与起始顶点P邻接的顶点到起始顶点的距离,并将它们放入集合B中。记录B中所有顶点的前继顶点为P. 将起始顶点P放入集合A中。
第一步:比较集合B中所有顶点到起始顶点的距离,选中其中距离起始顶点路径最短的顶点U放入集合A中;
第二步:重新计算集合B和集合C中与顶点U邻接的每一个顶点R到起始顶点的距离D(U)
+ 若R在集合B中,比较M(P,R)M(U,R)+D(U)的大小。如果M(P,R)<M(U,R)+D(U)D(R)Pre(R)不变;如果M(P,R)>M(U,R)+D(U)D(R)=M(U,R)+D(U)Pre(R)=U
+ 若R在集合C中,D(R)=M(U,R)+D(U)Pre(R)=U。并且将顶点R移入集合B中。
重复执行第一步和第二步,直到G中所有顶点均移入集合A中。

算法浅析

要弄清楚Dijkstra算法为什么能够确保找到的都是最短路径。主要需要弄清楚一个问题:
1. G的子图A中的任意顶点到顶点P的最短路径放在图G中仍然是最短路径;

问题1

A,B,C三个集合中顶点在图G中的邻接关系如下图所示:

在步骤二中每次集合A中加入新的顶点都会调整集合B中所有顶点Vi到达P的路径。从而保证了顶点Vi中存储的路径是图G的子图AVi中顶点Vi到达顶点P的最短路径。到这里我们无法保证该路径在图G中仍然是最短路径。所以回到第一步操作时我们只取集合B中记录路径距离最短的顶点U。顶点U所记录的到P的路径也是图G中的最短路径。因为如果不是的话,那么顶点UP的最短路径一定会经过集合B中的其他顶点,这就与前一次迭代的第二步操作相矛盾。

Java实现

// 图数据结构
public class Graph {
    private int vertex_num;

    private Vertex[] vertices;

    private double[][] adjacent_array;

    public Graph(int vertex_num) {
        this.vertex_num = vertex_num;
        this.adjacent_array = new double[vertex_num][vertex_num];
        this.vertices = new Vertex[vertex_num];
        for (int i = 0; i < vertex_num; i++) {
            this.vertices[i] = new Vertex();
        }
    }

    public int getVertex_num() {
        return vertex_num;
    }

    public void setVertex_num(int vertex_num) {
        this.vertex_num = vertex_num;
    }

    public double[][] getAdjacent_array() {
        return adjacent_array;
    }

    public void setAdjacent_array(double[][] adjacent_array) {
        this.adjacent_array = adjacent_array;
    }

    public Vertex[] getVertices() {
        return vertices;
    }

    public void setVertices(Vertex[] vertices) {
        this.vertices = vertices;
    }
}
// 顶点数据结构
public class Vertex {

    private int preIndex = -1;

    private double dist = Double.MAX_VALUE;

    private boolean isSelected = false;


    public double getDist() {
        return dist;
    }

    public void setDist(double dist) {
        this.dist = dist;
    }

    public boolean isSelected() {
        return isSelected;
    }

    public void setSelected(boolean selected) {
        isSelected = selected;
    }

    public int getPreIndex() {
        return preIndex;
    }

    public void setPreIndex(int preIndex) {
        this.preIndex = preIndex;
    }
}
// 算法实现
public class Dijkstra {

    public static Graph calMinimumPath(Graph g, int startIndex) {

        //init
        for (int i = 0; i < g.getVertex_num(); i++) {
            if (i == startIndex) {
                g.getVertices()[i].setDist(0);
                g.getVertices()[i].setPreIndex(-1);
                // 将起点加入集合A
                g.getVertices()[i].setSelected(true);
                continue;
            } else {
                if (g.getAdjacent_array()[i][startIndex] < Double.MAX_VALUE) {
                    g.getVertices()[i].setDist(g.getAdjacent_array()[i][startIndex]);
                    g.getVertices()[i].setPreIndex(startIndex);
                }
            }
        }

        for (int i = 0; i < g.getVertex_num(); i++) {
            // 从备选集合B中选择一个点加入集合A
            double min = Double.MAX_VALUE;
            int selected = Integer.MAX_VALUE;
            for (int j = 0; j < g.getVertex_num(); j++) {
                if (!g.getVertices()[j].isSelected() && g.getVertices()[j].getDist() < min) {
                    selected = j;
                    min = g.getVertices()[j].getDist();
                }
            }
            if (Double.MAX_VALUE == min) return g;
            // 将被选中的点加入集合A
            g.getVertices()[selected].setSelected(true);

            for (int k = 0; k < g.getVertex_num(); k++) {
                // 观察与被选中点S邻接的点R到目标点P的距离与R先到S再到P的距离的大小, 用小的替换
                if (!g.getVertices()[k].isSelected() && g.getAdjacent_array()[k][selected] < Double.MAX_VALUE) {

                    if (g.getAdjacent_array()[k][selected] + g.getVertices()[selected].getDist() < g.getVertices()[k].getDist()) {
                        // 说明加入点S之后R到P的距离比之前更近,需更新R点到P点的路径和距离. 该步骤也将集合C中与S邻接的点移入了集合B中
                        g.getVertices()[k].setDist(g.getAdjacent_array()[k][selected] + g.getVertices()[selected].getDist());
                        g.getVertices()[k].setPreIndex(selected);
                    }
                }
            }
        }
        return g;
    }

}
// 程序入口
public class MinimumPath {
    public static void main(String[] args) {
        int startIndex = 0;
        Graph g = new Graph(5);
        g.setAdjacent_array(new double[][]{{0, 100, 30, Double.MAX_VALUE, 10},
                                           {100, 0, 60, 10, Double.MAX_VALUE},
                                           {30, 60, 0, 60, Double.MAX_VALUE},
                                           {Double.MAX_VALUE, 10, 60, 0, 50},
                                           {10, Double.MAX_VALUE, Double.MAX_VALUE, 50, 0}});
        g = Dijkstra.calMinimumPath(g, startIndex);
        for (int i = 0; i < g.getVertex_num(); i++) {
            int current = i;
            while (g.getVertices()[current].getPreIndex() != -1) {
                System.out.print(current + " -> ");
                current = g.getVertices()[current].getPreIndex();
            }
            System.out.println(startIndex + " length: " + g.getVertices()[i].getDist());
        }
    }
}

输出结果:
0 length: 0.0
1 -> 3 -> 4 -> 0 length: 70.0
2 -> 0 length: 30.0
3 -> 4 -> 0 length: 60.0
4 -> 0 length: 10.0

有些地方可能想的太复杂了,导致语言表达不清晰,后面再慢慢改进。欢迎拍砖!!

转载自:https://blog.csdn.net/lnxyangruosong/article/details/78385523