漫画：图的最短路径问题

蔚落 2023-07-17 09:59 21阅读 0赞

![format_png][]

![format_png 1][]

**—————  第二天  —————**

![format_png 2][]

![format_png 3][]

![format_png 4][]

![format_png 5][]

![format_png 6][]

![format_png 7][]

如何遍历呢？

第一层，遍历顶点A：

![format_png 5][]

第二层，遍历A的邻接顶点B和C：

![format_png 8][]

第三层，遍历顶点B的邻接顶点D、E，遍历顶点C的邻接顶点F：

![format_png 9][]

第四层，遍历顶点E的邻接顶点G，也就是目标节点：

![format_png 10][]

由此得出，图中顶点A到G的（第一条）最短路径是A-B-E-G：

![format_png 11][]

![format_png 12][]

![format_png 13][]

换句话说，就是寻找从A到G之间，权值之和最小的路径。

![format_png 14][]

![format_png 15][]

![format_png 16][]

————————————

![format_png 17][]

![format_png 18][]

![format_png 19][]

![format_png 20][]

![format_png 21][]

![format_png 22][]

究竟什么是迪杰斯特拉算法？它是如何寻找图中顶点的最短路径呢？

这个算法的本质，是不断刷新起点与其他各个顶点之间的 “距离表”。

让我们来演示一下迪杰斯特拉的详细过程：

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

![format_png 23][]

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

![format_png 24][]

第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。把这一信息刷新到表中：

![format_png 25][]

接下来重复第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。把这一信息刷新到表中：

![format_png 26][]

（在第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**。把这一信息刷新到表中：

![format_png 27][]

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

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

![format_png 28][]

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

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

![format_png 29][]

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

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

/**
    
    * Dijkstra最短路径算法
    
    */
    
    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.vertexes.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 class Vertex {
    
    String data;
    
    Vertex(String data) {
    
    this.data = data;
    
    }
    
    }
    
    
    
    /**
    
    * 图的边
    
    */
    
    private static class Edge {
    
    int index;
    
    int weight;
    
    Edge(int index, int weight) {
    
    this.index = index;
    
    this.weight = weight;
    
    }
    
    }
    
    
    
    /**
    
    * 图
    
    */
    
    private static class Graph {
    
    private Vertex[] vertexes;
    
    private LinkedList<Edge> adj[];
    
    
    
    Graph(int size){
    
    //初始化顶点和邻接矩阵
    
    vertexes = new Vertex[size];
    
    adj = new LinkedList[size];
    
    for(int i=0; i<adj.length; i++){
    
    adj[i] = new LinkedList<Edge>();
    
    }
    
    }
    
    }
    
    
    
    private static void initGraph(Graph graph){
    
    graph.vertexes[0] = new Vertex("A");
    
    graph.vertexes[1] = new Vertex("B");
    
    graph.vertexes[2] = new Vertex("C");
    
    graph.vertexes[3] = new Vertex("D");
    
    graph.vertexes[4] = new Vertex("E");
    
    graph.vertexes[5] = new Vertex("F");
    
    graph.vertexes[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));
    
    }

![format_png 30][]

![format_png 31][]

![format_png 32][]

![format_png 33][]

![format_png 34][]

![format_png 35][]

![format_png 36][]

[format_png]: /images/20230528/0ca71ba3946e4466980867b3325367f3.png
[format_png 1]: /images/20230528/00241bb0c3b7439695ac2719b00b173a.png
[format_png 2]: /images/20230528/ee2e256ddfc046719c479f6c2ecde636.png
[format_png 3]: /images/20230528/d48624f5effb4e768519b6a99c3ab171.png
[format_png 4]: /images/20230528/cb07c77bccad486d9338e3d270ca1ccb.png
[format_png 5]: /images/20230528/f55e976155b64718b119cab583b5f8b4.png
[format_png 6]: /images/20230528/7c9ca932d48049d28c194216457b2c93.png
[format_png 7]: /images/20230528/cfa8d4e9ad7a4329b9471532b258906d.png
[format_png 8]: /images/20230528/24ae9eeac33b475ca5de2ff412d0b569.png
[format_png 9]: /images/20230528/d68965f2125642718378e0d877b94854.png
[format_png 10]: /images/20230528/88f86e149fbf441abcd1c7c0b8243564.png
[format_png 11]: /images/20230528/7a5ac3d85c404eaf8060f0e221cafa90.png
[format_png 12]: /images/20230528/9b0c8aa02dd242fba061e41a0b4fca39.png
[format_png 13]: /images/20230528/38d091fe7d4d436bae3d62af7befe9cd.png
[format_png 14]: /images/20230528/fc32bd94091b4e859320fb6e3f22ec97.png
[format_png 15]: /images/20230528/db01428dc4314a8b86e9aefad639ce18.png
[format_png 16]: /images/20230528/58e14d6f11874fb0a9fde542f6e43683.png
[format_png 17]: /images/20230528/fe1248b6a2b3421e8693c24606e56b68.png
[format_png 18]: /images/20230528/f714878e0f1a4b938b668aad15c1161d.png
[format_png 19]: /images/20230528/7165906f71ef43c1a436ac661cfb5232.png
[format_png 20]: /images/20230528/a67a0c71149a46f8a2e7c4c22f132656.png
[format_png 21]: /images/20230528/bff38517f09a466f8517cfa64e04e7f5.png
[format_png 22]: /images/20230528/76022cae05454f458f5bf76c38155255.png
[format_png 23]: /images/20230528/50d712c581c640188ce132df78823eea.png
[format_png 24]: /images/20230528/d73e8f39603845d8bff0e9e3108e34dc.png
[format_png 25]: /images/20230528/331be287a00b43b5852fcaef2d4020fd.png
[format_png 26]: /images/20230528/6cc08c6ad64f4692a737c5fe1655d399.png
[format_png 27]: /images/20230528/0d0d681a93e3405cbc1fc449bfe823fd.png
[format_png 28]: /images/20230528/9dfa8ae571014fab9de383ad2aa1c67c.png
[format_png 29]: /images/20230528/6c9cca7a3b3645fa975865ad6bd5292d.png
[format_png 30]: /images/20230528/8a06d2e20fd0453980805108ae9fe084.png
[format_png 31]: /images/20230528/f5b0b0b07bb14fca83050ad0b8901c99.png
[format_png 32]: /images/20230528/0d81e4592a0442d6b5f7a12f19012ce8.png
[format_png 33]: /images/20230528/0f9a8cd8b3c540f5a19efd39431145e9.png
[format_png 34]: /images/20230528/30137953e7a947ffa9558eb1278b6d23.png
[format_png 35]: /images/20230528/78f5bf671c434ceeb973a89fe6f89813.png
[format_png 36]: /images/20230528/df45d70082334fecbb8f8e3c69c30c87.png