侧边栏

图

发布于 2024-05-01 14:16:54| 分类于数据结构和算法

图也是一种常见的数据结构

最短路径

Dijkstra 算法

参考：

图文详解 Dijkstra 最短路径算法，使用图文详细展示了寻找相邻节点最短路径的策略

Dijkstra算法是一种用于计算图中从单个源顶点到所有其他顶点的最短路径的经典算法。该算法由荷兰计算机科学家艾兹赫尔·迪科斯彻在1956年提出，是解决最短路径问题中最为常用和有效的方法之一。

以下是Dijkstra算法的基本步骤：

初始化：将源顶点到所有其他顶点的距离初始化为无穷大，源顶点到自身的距离为0。
选择当前距离最短的顶点：从尚未处理的顶点中选择距离最短的顶点，将其标记为已处理。
更新距离：对于当前选定的顶点，遍历其所有邻居顶点，更新从源顶点到这些邻居顶点的距离。如果通过当前顶点到达邻居顶点的路径比之前计算的路径更短，则更新距离。
重复步骤2和3：重复选择当前距离最短的顶点，并更新距离，直到所有顶点都被标记为已处理，或者直到没有可达的顶点为止。

通过这些步骤，Dijkstra算法能够找到从源顶点到所有其他顶点的最短路径。该算法的关键在于使用贪心策略，每次选择当前距离最短的顶点进行处理，因此可以确保在每一步选择时，已经计算出的最短路径不会被改变。

以下面的图为例，从节点1开始，相邻节点有

2，长度为3
4，长度为1
6，长度为4

因此，下一步最近的选择是节点4，只需要长度为1就可以到达，其他的到达4的任何路径都不能比从节点1直接到达还小，这样就可以一直循环下去，更新从节点1到达每一个节点的最短路径

需要注意的是，Dijkstra算法仅适用于边权重为非负的图。如果图中存在负权边，可以考虑使用其他算法，如贝尔曼-福特算法。

比如743. 网络延迟时间这道题目

var networkDelayTime = function (times, n, k) {
    var g = new Array(n).fill(0).map(() => new Array())
    for (const [x, y, t] of times) {
        g[x - 1].push([y, t])
    }

    const queue = new MinPriorityQueue()
    queue.enqueue(k, 0)
    let dis = new Array(n).fill(Infinity)
    dis[k - 1] = 0
    while (!queue.isEmpty()) {
        const { element: x, priority: cost } = queue.dequeue()
         if (cost > dis[x - 1]) continue
        for (const [y, t] of g[x - 1]) {
            const v = cost + t
            if (dis[y - 1] > v) {
                dis[y - 1] = v
                queue.enqueue(y, v)
            }
        }
    }
    const max = Math.max(...dis)
    return max === Infinity ? -1 : max
}

bellman ford

787. K 站中转内最便宜的航班

#图

你要请我喝一杯奶茶？

本站文章均为本人原创，参考文章我都会在文中进行声明，也请您转载时附上署名。

图

最短路径 ​

Dijkstra 算法 ​

bellman ford ​

你要请我喝一杯奶茶？

最短路径

Dijkstra 算法

bellman ford