最短路径Dijkstra算法

大家好！今天我想给大家讲一个非常有趣的算法，叫做Dijkstra算法。这个算法可以帮助我们在图中找到从一个点到另一个点的最短路径，就好像我们在玩一个寻找宝藏的游戏！

故事开始

想象你住在一个湖边，湖上有很多小岛，每个小岛之间都有桥连接，但是这些桥的长度不一样，有的很短，有的很长。现在，你有一个最好的朋友住在其中一个小岛上，你想去他家玩，但是你想找一条最短的路线，因为这样走得快，而且还可以省点力气。

怎么做呢？

1. 第一步：你先看看你家周围的桥，哪座桥最短？你决定先去那个离你家最近的小岛。比如说，这个小岛叫小岛A。

2. 第二步：到了小岛A后，你再看看从这里去其他小岛的桥，哪一座最短？如果去小岛B的桥是最短的，你就记下这条路线（你家 -> 小岛A -> 小岛B）。

3. 第三步：现在你知道去小岛B的路了，但你还想知道去其他小岛的最短路线。假设你发现小岛B到小岛C的桥很短，于是你又记下这条路线（你家 -> 小岛A -> 小岛B -> 小岛C）。

4. 继续这样做：你每次选择最短的桥去下一个小岛，不断更新你知道的最短路线，直到你到达你朋友的小岛。

关键点

• 每次只选择最短的路线：就像你每次都选择最短的桥一样，Dijkstra算法每次都选择到目前为止最短的路径去探索。
• 更新路径：如果你发现通过一个新的小岛可以更快地到达另一个小岛，你会更新你记录的路线。
• 标记已访问的小岛：你每次到达一个新的小岛后，你会标记这个小岛为“已访问”，这样你就不会再回到这里重新探索。

完整案例

让我们来看一个具体的例子吧。假设你住在湖边，湖中有五个小岛A、B、C、D、E，桥的长度如下：

• 你家到A：5步
• A到B：3步
• A到C：2步
• B到C：1步
• B到D：2步
• C到D：6步
• C到E：4步
• D到E：1步
• E到你朋友家：3步

目标：从你家到你朋友家找最短路径。

1. 起点：从你家开始，离你最近的小岛是A（5步）。

2. 第一轮探索：

   • 从A到B：3步（总共8步）
   • 从A到C：2步（总共7步）
   • 标记A为已访问。

3. 第二轮探索：

   • 从C到B：1步（总共8步）
   • 从C到D：6步（总共13步）
   • 从C到E：4步（总共11步）
   • 标记C为已访问。

4. 第三轮探索：

   • 从B到D：2步（总共10步）
   • 标记B为已访问。

5. 第四轮探索：

   • 从D到E：1步（总共11步）
   • 标记D为已访问。

6. 第五轮探索：

   • 从E到你朋友家：3步（总共14步）
   • 标记E为已访问。

结果：最短路径是：你家 -> A -> C -> E -> 你朋友家，共需14步。

Java实现

下面是一个使用Java实现的Dijkstra算法的例子，它展示了如何将这个寻找最短路径的过程用代码表达出来：

import java.util.*;

public class DijkstraAlgorithm {

    private static final int NO_PARENT = -1;

    // Dijkstra算法的核心实现
    public static void dijkstra(int[][] adjacencyMatrix, int startVertex) {
        int nVertices = adjacencyMatrix[0].length;

        // 初始化距离数组和已访问数组
        int[] shortestDistances = new int[nVertices];
        boolean[] added = new boolean[nVertices];
        int[] parents = new int[nVertices];

        // 初始化所有距离为无限大
        for (int vertexIndex = 0; vertexIndex < nVertices; vertexIndex++) {
            shortestDistances[vertexIndex] = Integer.MAX_VALUE;
            added[vertexIndex] = false;
        }

        // 起点到自己的距离是0
        shortestDistances[startVertex] = 0;
        parents[startVertex] = NO_PARENT;

        // 找出所有顶点的最短路径
        for (int i = 1; i < nVertices; i++) {
            // 选择距离最短且未被处理的顶点
            int nearestVertex = -1;
            int shortestDistance = Integer.MAX_VALUE;
            for (int vertexIndex = 0; vertexIndex < nVertices; vertexIndex++) {
                if (!added[vertexIndex] && shortestDistances[vertexIndex] < shortestDistance) {
                    nearestVertex = vertexIndex;
                    shortestDistance = shortestDistances[vertexIndex];
                }
            }

            // 标记该顶点为已处理
            added[nearestVertex] = true;

            // 更新邻居顶点的距离
            for (int vertexIndex = 0; vertexIndex < nVertices; vertexIndex++) {
                int edgeDistance = adjacencyMatrix[nearestVertex][vertexIndex];

                if (edgeDistance > 0 && ((shortestDistance + edgeDistance) < shortestDistances[vertexIndex])) {
                    parents[vertexIndex] = nearestVertex;
                    shortestDistances[vertexIndex] = shortestDistance + edgeDistance;
                }
            }
        }

        // 打印结果
        printSolution(startVertex, shortestDistances, parents);
    }

    // 打印解决方案
    private static void printSolution(int startVertex, int[] distances, int[] parents) {
        int nVertices = distances.length;
        System.out.print("Vertex\t Distance\tPath");

        for (int vertexIndex = 0; vertexIndex < nVertices; vertexIndex++) {
            if (vertexIndex != startVertex) {
                System.out.print("\n" + startVertex + " -> ");
                System.out.print(vertexIndex + " \t\t ");
                System.out.print(distances[vertexIndex] + "\t\t");
                printPath(vertexIndex, parents);
            }
        }
    }

    // 打印路径
    private static void printPath(int currentVertex, int[] parents) {
        // 基础情况：如果到达了起点，返回
        if (currentVertex == NO_PARENT) {
            return;
        }
        printPath(parents[currentVertex], parents);
        System.out.print(currentVertex + " ");
    }

    // 主函数
    public static void main(String[] args) {
        int[][] adjacencyMatrix = {
                {0, 5, 0, 0, 0, 0},
                {5, 0, 3, 2, 0, 0},
                {0, 3, 0, 1, 2, 0},
                {0, 2, 1, 0, 6, 4},
                {0, 0, 2, 6, 0, 1},
                {0, 0, 0, 4, 1, 0}
        };
        dijkstra(adjacencyMatrix, 0); // 从顶点0（你家）开始
    }
}

这个Java代码实现了Dijkstra算法的核心逻辑：

• 首先，我们初始化了一个距离数组shortestDistances来记录从起点到每个顶点的最短距离，一个布尔数组added来标记已经处理过的顶点，以及一个parents数组来记录最短路径树的结构。
• 然后，我们从起点开始，逐步选择距离最短且未被处理的顶点，并更新其邻居的距离。
• 最后，通过printSolution函数打印出从起点到每个顶点的最短路径和距离。

这个代码模拟了你在寻找最短路径时的过程，选择最短的路线，不断更新路径，直到到达终点。希望这个解释和代码能帮助大家更好地理解Dijkstra算法的原理和实现！