Kotlin中实现迪杰斯特拉算法

Kahen大约 6 分钟

Kotlin中实现迪杰斯特拉算法

在本教程中，我们将学习如何在Kotlin中实现迪杰斯特拉算法。它是一种在加权图中找出从起始节点到所有其他节点的最短路径的解决方案。与适用于无权图的广度优先搜索（BFS）不同，迪杰斯特拉算法在有加权边的环境中表现出色，根据累积权重或距离优化路径。本文深入探讨了在Kotlin中实现迪杰斯特拉算法，展示了该语言简洁的语法和强大的功能。

2. 理解迪杰斯特拉算法

迪杰斯特拉算法擅长在有加权边的图中找到从起始节点到所有其他节点的最短路径。它将起始节点的距离初始化为零，其他节点的距离初始化为无穷大，迭代更新距离，并按距离的升序处理节点。

迪杰斯特拉算法在包含正权重的有向和无向图中表现最佳。它不适用于包含负边权重的图，因为这些可能导致路径长度计算的不一致，可能引起无限循环。此外，算法在包含环或断开的段的图中可能不会按预期执行，需要额外的检查或修改以处理这些复杂性。

3. 在Kotlin中实现迪杰斯特拉算法

迪杰斯特拉算法从将起始节点的距离设置为零，其他所有节点的距离设置为无穷大开始。它迭代地选择未访问的、从起始节点出发已知距离最小的节点，更新其相邻节点的距离，并重复此过程，直到所有节点都被访问。这种对下一个最近节点的优先级与BFS逐层探索相邻节点形成鲜明对比，需要一个优先队列来有效管理节点处理。

3.1. 定义图

要实现迪杰斯特拉算法，我们首先需要一个有加权边的图。我们在Kotlin中使用邻接表来表示这个图，其中每个节点与一个列表相关联。列表中的每个对包含一个连接的节点和它们之间边的权重。下面是这样一个图的视觉表示：

基于这种结构，我们可以在Kotlin中这样定义我们的图：

val graph = mapOf``<Int, List<Pair````<Int, Int>``````>>(
    1 to listOf(Pair(2, 10), Pair(3, 15)),
    2 to listOf(Pair(4, 12)),
    3 to listOf(Pair(4, 15)),
    4 to listOf(Pair(5, 12), Pair(6, 15)),
    5 to emptyList(),
    6 to emptyList()
)

这个邻接表允许我们高效地存储和访问图的连接和权重。这是我们实现迪杰斯特拉算法的基础。

3.2. 算法

有了我们的图结构，我们深入到算法中。一个优先队列和一个距离映射是关键，存储发现的最短距离和控制节点处理顺序：

fun dijkstra(graph: Map``<Int, List<Pair````<Int, Int>``````>>, start: Int): Map````<Int, Int>```` {
    val distances = mutableMapOf````<Int, Int>````().withDefault { Int.MAX_VALUE }
    val priorityQueue = PriorityQueue<Pair````<Int, Int>````>(compareBy { it.second }).apply { add(start to 0) }

    distances[start] = 0

    while (priorityQueue.isNotEmpty()) {
        val (node, currentDist) = priorityQueue.poll()
        graph[node]?.forEach { (adjacent, weight) ->
            val totalDist = currentDist + weight
            if (totalDist < distances.getValue(adjacent)) {
                distances[adjacent] = totalDist
                priorityQueue.add(adjacent to totalDist)
            }
        }
    }
    return distances
}

在这个实现中，distances映射存储从起始节点到每个其他节点的最短路径，初始化默认值为_Int.MAX_VALUE_。一个优先_queue_按它们的距离对节点进行排序，确保它首先处理最近的节点。当算法处理节点时，如果它发现一条更短的路径，它会更新每个节点的邻居的距离映射，不断细化路径，直到它确立到所有节点的最短距离。

3.3. 处理环

在Kotlin中实现迪杰斯特拉算法时，我们必须特别考虑处理包含环的图。图中的环可能会使最短路径的计算复杂化，因为它们允许以可能更低的累积权重重新访问节点。确保我们的实现有效地管理这些场景以保持算法的准确性并防止执行期间的无限循环至关重要。处理Dijkstra中的环时有以下三个主要步骤：

检测环：在算法执行期间，我们应该检查一个节点是否已经被访问过，并且如果再次访问它是否会提供一条更短的路径。如果一个节点被重新访问并且没有发现更短的路径，它就不应该再次被添加到优先队列中。
更新距离：如果检测到环并且重新访问节点导致了一条更短的路径，应该更新到这个节点的距离，并且应该使用新距离重新将节点入队。这确保算法始终考虑到达每个节点的最短路径，即使那条路径涉及穿越一个环。
防止无限循环：为了防止算法陷入无限循环，我们可以维护一个集合，跟踪每个节点以及它被添加到队列时的距离。在将节点重新添加到队列之前，检查它是否存在于集合中，并且具有更高的距离。如果没有，重新入队节点是安全的；否则，跳过添加它以防止冗余操作。

让我们调整我们的算法并创建_dijkstraWithLoops()_：

fun dijkstraWithLoops(graph: Map``<Int, List<Pair````<Int, Int>``````>>, start: Int): Map````<Int, Int>```` {
    val distances = mutableMapOf````<Int, Int>````().withDefault { Int.MAX_VALUE }
    val priorityQueue = PriorityQueue<Pair````<Int, Int>````>(compareBy { it.second })
    val visited = mutableSetOf<Pair````<Int, Int>````>()

    priorityQueue.add(start to 0)
    distances[start] = 0

    while (priorityQueue.isNotEmpty()) {
        val (node, currentDist) = priorityQueue.poll()
        if (visited.add(node to currentDist)) {
            graph[node]?.forEach { (adjacent, weight) ->
                val totalDist = currentDist + weight
                if (totalDist < distances.getValue(adjacent)) {
                    distances[adjacent] = totalDist
                    priorityQueue.add(adjacent to totalDist)
                }
            }
        }
    }
    return distances
}

4. 测试

为了验证我们迪杰斯特拉算法的实现，我们创建了一个反映我们图结构的测试场景：

@Test
fun `Should calculate shortest path when using Dijkstra algorithm`() {
    val graph = mapOf(
        1 to listOf(Pair(2, 10), Pair(3, 15)),
        2 to listOf(Pair(4, 12)),
        3 to listOf(Pair(4, 15)),
        4 to listOf(Pair(5, 12), Pair(6, 15)),
        5 to emptyList(),
        6 to emptyList()
    )

    val shortestPaths = dijkstra(graph, 1)

    assertEquals(37, shortestPaths.getValue(6))
}

在这个测试中，我们断言从节点_1_到节点_6_的最短路径是_37_，展示了算法计算最小距离的能力。通过单元测试，我们确保了迪杰斯特拉算法在Kotlin中的实现的可靠性和效率。

6. 结论

Kotlin中的迪杰斯特拉算法为在加权图中找到最短路径提供了一种强大而有效的方法。通过利用Kotlin的特性，我们可以清晰而精确地实现这个经典算法，从而开发出复杂的应用程序。如常，本文中使用的代码可以在GitHub上找到。