最短路径算法补充版

原创

疯狂的KK

发布于 2023-07-20 11:55:52

1960

发布于 2023-07-20 11:55:52

文章被收录于专栏：Java项目实战Java项目实战

最短路径算法（Dijkstra Algorithm）的原理

最短路径算法是一种用于寻找图中两个顶点之间最短路径的算法。最短路径可以根据路径上边的权重进行比较。Dijkstra算法是最常用和最流行的最短路径算法之一。它被广泛应用于网络路由算法、地图导航等领域。

Dijkstra算法的基本原理是从起点开始，逐步计算出到其他各个顶点的最短路径，并在计算的过程中维护一个待确定的最短路径集合。具体步骤如下：

创建一个顶点集合，将起点添加到集合中。
初始化一个距离数组，用于存储起点到各个顶点的距离（初始时，起点到自身的距离为0，其他顶点的距离为正无穷）。
从起点开始，遍历起点的邻接顶点，并更新距离数组中的距离值。如果通过该邻接顶点可以获得更短的距离，则更新距离数组中对应顶点的值。
在未确定最短路径的顶点中，选择距离最小的顶点，将其添加到已确定最短路径的集合中。
重复步骤3和步骤4，直到所有顶点都被添加到已确定最短路径的集合中，或者找到目标顶点的最短路径。

最终，通过该算法可以得到起点到其他各个顶点的最短路径以及对应的距离。

最短路径问题的解决示例

为了更好地理解和演示Dijkstra算法的原理，我们将使用一个简单的例子来解决最短路径问题。

假设有以下图表示的网络，其中顶点表示城市，边表示城市之间的道路，每条边上的数字表示道路的长度。

我们的目标是找到城市A到其他各个城市的最短路径。

首先，我们使用邻接矩阵表示图，并初始化距离数组：

int[][] graph = {
    {0, 2, 4, 0, 0, 0},
    {2, 0, 1, 7, 0, 0},
    {4, 1, 0, 6, 8, 0},
    {0, 7, 6, 0, 3, 9},
    {0, 0, 8, 3, 0, 5},
    {0, 0, 0, 9, 5, 0}
};

int[] distance = new int[graph.length];
Arrays.fill(distance, Integer.MAX_VALUE);
distance[0] = 0;

接下来，我们使用Dijkstra算法计算最短路径：

boolean[] visited = new boolean[graph.length];

for (int i = 0; i < graph.length - 1; i++) {
    int minDistance = Integer.MAX_VALUE;
    int minIndex = -1;

    for (int j = 0; j < graph.length; j++) {
        if (!visited[j] && distance[j] < minDistance) {
            minDistance = distance[j];
            minIndex = j;
        }
    }

    visited[minIndex] = true;

    for (int j = 0; j < graph.length; j++) {
        if (!visited[j] && graph[minIndex][j] != 0 && distance[minIndex] + graph[minIndex][j] < distance[j]) {
            distance[j] = distance[minIndex] + graph[minIndex][j];
        }
    }
}

在上面的代码中，我们使用visited数组来跟踪已确定最短路径的顶点，初始时全部为false。

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

编程算法