迪杰斯特拉(Dijkstra's )算法——解决带权有向无向图最短路径

这篇具有很好参考价值的文章主要介绍了迪杰斯特拉(Dijkstra's )算法——解决带权有向无向图最短路径。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

迪杰斯特拉算法(Dijkstra's Algorithm),又称为狄克斯特拉算法,是一种用于解决带权重有向图或无向图最短路径问题的算法。该算法由荷兰计算机科学家艾兹赫尔·狄克斯特拉在1956年发明,是一种广泛应用于网络路由和其他领域的算法。


狄杰斯特拉算法可以用于带权无向图求最短路径吗,算法

在 2001 年的一次采访中,Dijkstra 博士透露了他设计这个算法的起因和过程:

从 Rotterdam 到 Groningen 的最短路线是什么?我花了大概 20 分钟时间设计了这个寻找最短路径的算法。一天早上我正和我年轻的未婚妻在 Amsterdam 逛街,觉得有点累了,我们就坐在咖啡厅的露台上喝了一杯咖啡,我在想是否能够解决这个问题,然后,我设计出了这个最短路径算法。我说过,这是一个 20 分钟的设计。事实上,三年之后的 1959 年它才被发布,现在看来依然很不错,其原因之一是我当时设计的时候没有纸和笔,从而不得不极力避免所有可避免的复杂性。最终,令我惊讶的是,这个算法成为了我成名的基石之一。——引自文章《An interview with Edsger W. Dijkstra》.

一、 算法原理

迪杰斯特拉算法的核心思想是:假设当前已知从起点到某点的最短路径为已经确定的最短路径,然后通过不断扩展已知的最短路径来逐步得到起点到其他所有点的最短路径。

具体来说,算法如下:

初始化算法

  • 选定一个起点s,并初始化一个距离数组dist,其中dist[i]表示起点s到节点i的最短距离,初始时将所有元素设置为正无穷。
  • 记录一个集合S,代表已经求出最短路径的节点集合,初始时S只包含起点s。
  • 对于每个节点i,记录一个前驱节点prev[i],表示从起点s到节点i的最短路径上i的前一个节点,初始时将所有元素设置为-1。

循环求解

  • 从距离数组dist中找出不属于集合S且距离最近的节点u,将其加入集合S中。
  • 对于节点u的所有邻接节点v,更新它们的最短距离和前驱节点:
  • 如果通过u到达v的距离比当前已知的最短距离更小,则更新dist[v]和prev[v]。
  • 否则保持dist[v]和prev[v]不变。
  • 如果集合S包含所有节点(即已经找到了起点到所有节点的最短路径),算法结束。

输出结果

  • 根据prev数组可以重构出起点到每个节点的最短路径。

二、 算法实现

下面给出C++语言实现的迪杰斯特拉算法示例代码:

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int INF = 0x3f3f3f3f;  // 定义正无穷

// 定义图的邻接表表示
typedef pair<int, int> P;   // first表示节点编号,second表示边权值
vector<vector<P>> graph;

// 迪杰斯特拉算法函数
void dijkstra(int start, vector<int>& dist, vector<int>& prev) {
    int n = graph.size();
    dist.resize(n, INF);
    prev.resize(n, -1);

    dist[start] = 0;
    prev[start] = start;

    priority_queue<P, vector<P>, greater<P>> pq;   // 小根堆,存储节点编号和距离
    pq.push(make_pair(start, 0));

    while (!pq.empty()) {
        P p = pq.top();
        pq.pop();

        int u = p.first, d = p.second;
        if (dist[u] < d) continue;

        for (int i = 0; i < graph[u].size(); i++) {
            int v = graph[u][i].first, w = graph[u][i].second;
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                prev[v] = u;
                pq.push(make_pair(v, dist[v]));
            }
        }
    }
}

// 测试代码
int main() {
    int n = 5;   // 节点数
    graph.resize(n);

    // 初始化图
    graph[0].push_back(make_pair(1, 2));
    graph[0].push_back(make_pair(2, 4));
    graph[1].push_back(make_pair(2, 1));
    graph[1].push_back(make_pair(3, 2));
    graph[2].push_back(make_pair(3, 3));
    graph[2].push_back(make_pair(4, 2));
    graph[3].push_back(make_pair(4, 5));

    // 运行算法
    vector<int> dist, prev;
    dijkstra(0, dist, prev);

    // 输出结果
    for (int i = 0; i < n; i++) {
        cout << "Node " << i << ": ";
        if (dist[i] == INF) {
            cout << "Unreachable" << endl;
        } else {
            cout << "Distance = " << dist[i] << ", Path = ";
            int j = i;
            while (prev[j] != j) {
                cout << j << " <- ";
                j = prev[j];
            }
            cout << j << endl;
        }
    }

    return 0;
}

在上面的代码中,我们首先定义了一个邻接表graph来表示图。每个元素graph[i]是一个vector数组,表示节点i的邻接节点和对应的边权值。

然后,我们实现了dijkstra()函数来执行迪杰斯特拉算法。该函数接受三个参数:起点start,以及两个输出参数dist和prev,分别表示节点到起点的最短距离和前驱节点。

在函数内部,我们先初始化dist和prev数组,将所有元素分别设为正无穷和-1。然后,我们创建一个小根堆pq(用STL中的priority_queue实现),用来存储节点编号和距离。将起点加入小根堆中,距离设为0。

接下来,我们不断从小根堆中取出距离最近的节点u,并更新它的所有邻接节点v的最短距离和前驱节点。如果新的距离比当前已知的最短距离更小,则将v加入小根堆中,并更新dist[v]和prev[v]。

最后,我们输出每个节点到起点的最短距离和路径。如果节点不可达,则输出Unreachable。需要注意的是,在重构路径时,我们可以通过prev数组从终点出发往前逐个查找前驱节点,以构建完整路径。

狄杰斯特拉算法可以用于带权无向图求最短路径吗,算法

假设有如下的图示例,包含6个节点和它们之间的边:

节点: 0 1 2 3 4 5
边: (0, 1, 4), (0, 2, 2), (1, 3, 2), (1, 2, 1), (2, 3, 5), (2, 4, 6), (3, 4, 1), (3, 5, 3), (4, 5, 4)

现在,我们设定起点为节点0,终点为节点5。让我们通过迪杰斯特拉算法来找到起点0到终点5的最短路径。

首先,我们初始化距离数组dist和前驱数组prev:

dist: [0, INF, INF, INF, INF, INF]
prev: [-1, -1, -1, -1, -1, -1]

然后,我们从起点0开始,将其加入集合S,并更新与起点相邻的节点的最短距离和前驱节点。

迭代1:节点0的邻接节点是节点1和节点2,它们与起点0的距离分别为4和2。由于这两个距离比当前已知的距离要小,所以我们更新dist和prev:

dist: [0, 4, 2, INF, INF, INF]
prev: [-1, 0, 0, -1, -1, -1]

迭代2:下一步我们需要选择距离起点0最近的节点,也就是节点2(距离为2)。将节点2加入集合S,并更新与节点2相邻的节点的最短距离和前驱节点。

节点2的邻接节点是节点1、节点3和节点4,它们与起点的距离分别为3、7和8。由于节点1的距离比当前已知的距离要小,所以我们更新dist和prev:

dist: [0, 3, 2, INF, INF, INF]
prev: [-1, 2, 0, -1, -1, -1]

迭代3:下一步选择距离起点0最近的节点,也就是节点1(距离为3)。将节点1加入集合S,并更新与节点1相邻的节点的最短距离和前驱节点。

节点1的邻接节点是节点3和节点2,它们与起点的距离分别为5和4。由于节点3的距离比当前已知的距离要小,所以我们更新dist和prev:

dist: [0, 3, 2, 5, INF, INF]
prev: [-1, 2, 0, 1, -1, -1]

迭代4:下一步选择距离起点0最近的节点,也就是节点3(距离为5)。将节点3加入集合S,并更新与节点3相邻的节点的最短距离和前驱节点。

节点3的邻接节点是节点4和节点5,它们与起点的距离分别为6和8。由于节点4的距离比当前已知的距离要小,所以我们更新dist和prev:

dist: [0, 3, 2, 5, 7, INF]
prev: [-1, 2, 0, 1, 3, -1]

迭代5:下一步选择距离起点0最近的节点,也就是节点4(距离为7)。将节点4加入集合S,并更新与节点4相邻的节点的最短距离和前驱节点。

节点4的邻接节点是节点3和节点5,它们与起点的距离分别为6和11。由于节点3的距离比当前已知的距离要小,所以我们更新dist和prev:

dist: [0, 3, 2, 5, 6, INF]
prev: [-1, 2, 0, 1, 3, 4]

迭代6:最后一个节点是终点5,我们将其加入集合S,并完成算法。

此时,起点0到终点5的最短路径为:0 -> 2 -> 1 -> 3 -> 4 -> 5,总距离为6。

这就是迪杰斯特拉算法的演示过程。通过不断更新最短距离和前驱节点,我们可以找到起点到终点的最短路径。

三、 算法优化

尽管迪杰斯特拉算法已经在实践中证明了其效率和可靠性,但它仍然存在一些优化空间,以进一步提高算法效率。

堆优化

上面我们介绍的算法实现方式使用了小根堆来存储节点编号和距离信息。这样做可以确保我们每次取出的节点都是距离起点最近的。但在节点数较多的情况下,堆的维护和调整成本会很高,影响算法效率。

针对这个问题,我们可以采用更快的数据结构来存储节点信息。例如,我们可以使用斐波那契堆(Fibonacci Heap)或二项堆(Binomial Heap)等高效的堆实现方式来优化算法。

并行计算

迪杰斯特拉算法是一种基于图的算法,因此可以将其分布式计算,以提高计算效率。

例如,我们可以利用MapReduce等分布式计算框架,在多个计算节点上并行执行迪杰斯特拉算法,并在最后将结果汇总。通过这种方式,我们可以显著缩短计算时间,提高算法效率。

基于GPU的优化

由于迪杰斯特拉算法涉及大量的图数据处理和距离计算,因此GPU(Graphics Processing Unit)可以被用来加速算法运行。通过将算法并行化,将图划分到多个GPU处理单元上,我们可以显著提高算法效率。

四、 结论

迪杰斯特拉算法是一种用于解决带权重有向图或无向图最短路径问题的经典算法。该算法基于贪心策略,通过不断扩展已知的最短路径来逐步得到起点到其他所有点的最短路径。

在实际应用中,我们常常需要对算法进行优化,以提升算法效率和性能。例如,我们可以采用更快的堆实现方式、并行计算和GPU加速等方法,以进一步提高算法效率。文章来源地址https://www.toymoban.com/news/detail-771278.html

到了这里,关于迪杰斯特拉(Dijkstra's )算法——解决带权有向无向图最短路径的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • C语言 最短路径 迪杰斯特拉(Dijkstra)算法

    迪杰斯特拉(Dijkstra)算法是由荷兰计算机科学家狄克斯特拉于1959年提出的,因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法,解决的是有权图中单源最短路径问题。迪杰斯特拉算法主要特点是从起始点开始,采用贪心算法的策略,每次遍历到始点距离最

    2024年02月03日
    浏览(39)
  • 堆优化版迪杰斯特拉(Dijkstra)算法简单分析

    优化原理: 上面的朴素版迪杰斯特拉算法主要缺陷是,每当找到一个最短路径,如果需要找下一个最短路径,就需要在完成松弛操作之后,遍历dist数组,寻找其中的最小值。遍历dist数组的时间复杂度为O(n)。(dist数组储存源点到各个点的当前最短距离) 如果图的边数为n*(

    2023年04月08日
    浏览(46)
  • java实现迪杰斯特拉(Dijkstra)算法求解最短路问题

    迪杰斯特拉(Dijkstra)算法是由荷兰计算机科学家狄克斯特拉于1959年提出的。是寻找从一个顶点到其余各顶点的最短路径算法,可用来解决最短路径问题。 迪杰斯特拉算法采用贪心算法的策略,将所有顶点分为已标记点和未标记点两个集合,从起始点开始,不断在未标记点中寻

    2024年02月12日
    浏览(37)
  • 【数据结构】图解:迪杰斯特拉算法(Dijkstra)最短路径

    目录 一、方法描述 二、例题一  ​编辑 三、例题二  有图如上,用迪杰斯特拉算法求顶点A到其余各顶点的最短路径,请问1.第一步求出的最短路径是A到C的最短路径2.第二步求出的是顶点A到顶点B/F的最短路径3.顶点A到D的最短路径长度是__25___ (填数字)4.顶点A到顶点F的最短路

    2024年02月12日
    浏览(35)
  • 大话数据结构-迪杰斯特拉算法(Dijkstra)和弗洛伊德算法(Floyd)

      最短路径,对于图来说,是两顶点之间经过的边数最少的路径;对于网来说,是指两顶点之间经过的边上权值之和最小的路径。路径上第一个顶点为源点,最后一个顶点是终点。   以如下无向图为例:   我们来计算下标为0的顶点,到其他顶点的最短路径,首先定义

    2024年02月06日
    浏览(39)
  • MATLAB轻松绘制地图路线——Dijkstra(迪杰斯特拉)算法最短路径规划

    利用MATLAB绘制地图需要三个基本数据: 节点 节点坐标 节点间相通的路线 以11B交通巡警平台调度问题中的A区数据为例: (数据及工程文件下载链接见文末) Demo1: 可通过已知节点的坐标,计算出各节点之间的距离,有Matlab基础的同学可以尝试Demo2, 也可通过Excel自行实现;

    2023年04月21日
    浏览(46)
  • 数据结构 -最短路径dijkstra(迪杰斯特拉)算法讲解及代码实现

            迪杰斯特拉算法是一种广义的贪心算法,求出局部最优解,再去求全局最优解 举例图:(起始点为1) 辅助数组: s:记录了目标顶点到其他顶点的最短路径是否求得(求得为1,否则为0) p:目标顶点到其他顶点的最短路径的前驱节点 (如,求得1-7-5的最短路径,那

    2024年02月11日
    浏览(34)
  • 数据结构与算法 —— 最短路径Dijkstra算法(迪杰斯特拉)详细图解以及python实现

    目录 前言 1. 介绍 2. 加权图 2.1 概念 3. 最短路径 -- Dijkstra 算法 3.1 历史 3.2 Dijkstra 算法的基本思路 3.3 Dijkstra 算法图解 4.  python中dijkstra算法的实现 5. 总结  前两章我们讲到了关于图的基本知识,和广度/深度优先搜索。 本章,我们将介绍 加权图 和 最短路径 的相关知识。 最

    2024年02月12日
    浏览(51)
  • 使用omp并行技术加速最短路径算法-迪杰斯特拉(Dijkstra)算法(记录最短路径和距离)

    原理: Dijkstra算法是解决**单源最短路径**问题的**贪心算法** 它先求出长度最短的一条路径,再参照该最短路径求出长度次短的一条路径     直到求出从源点到其他各个顶点的最短路径。 首先假定源点为u,顶点集合V被划分为两部分:集合 S 和 V-S。 初始时S中仅含有源点u,

    2024年02月10日
    浏览(47)
  • 【数据结构】最小生成树(Prim算法,普里姆算法,普利姆)、最短路径(Dijkstra算法,迪杰斯特拉算法,单源最短路径)

    问题解答 (1)最小生成树(Minimal Spanning Tree)的定义 生成树的代价 :设 G ( V , E ) G(V,E) G ( V , E ) 是一个无向连通网图,生成树上 各边的权值之和 称为 生成树的代价 。 最小生成树 :在图 G G G 所有生成树中, 代价最小的生成树 为 最小生成树 。 (2)最小生成树(MST)的性

    2024年02月11日
    浏览(38)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包