首页 > 编程语言 >Dijkstra 算法——求解最短路径问题

Dijkstra 算法——求解最短路径问题

时间:2023-07-25 16:44:47浏览次数:39  
标签:dist int 算法 最短 start Dijkstra vector path 顶点

Dijkstra 算法——求解最短路径问题

  迪杰斯特拉算法(Dijkstra's algorithm)是一种用于解决单源最短路径问题的贪心算法。它可以找到从一个起始顶点到其他所有顶点的最短路径,并且适用于边的权重非负的图。

算法步骤如下:

  1. 创建一个数组 dist,用于保存起始顶点到其他顶点的最短距离。初始化 dist 数组,将起始顶点的距离设置为0,其他顶点的距离设置为无穷大(或者一个很大的值)。
  2. 创建一个集合 visited,用于记录已经确定最短路径的顶点。
  3. 重复以下步骤,直到所有顶点都在 visited 集合中:
    a. 从 dist 数组中选择当前距离最小的顶点 u,将其加入 visited 集合。
    b. 对于 u 的所有未访问的邻居顶点 v,更新其距离:dist[v] = min(dist[v], dist[u] + weight(u, v)),其中 weight(u, v) 表示边 (u, v) 的权重。
  4. 最终,dist 数组中存储的就是起始顶点到其他所有顶点的最短距离。

  本质上是维护两个集合,S 集合表示已处理的点,U 集合表示未处理的点。每次把一个点从 U 放到 S 里,同时要更新 S 中的点到 U 中的点的距离。直到 U 中没有点。

  Dijkstra 算法的关键点在于每次选择距离最小的顶点并更新与该顶点相邻的顶点的距离,这样逐步扩展最短路径。算法的正确性基于贪心策略:每次找到距离最小的顶点,该顶点的最短路径已经确定,不再需要重新访问。

  需要注意的是,Dijkstra 算法要求边的权重非负。如果存在负权边,应该使用 Bellman-Ford 算法来解决单源最短路径问题。

c++代码示例

vector<int> dijkstra(const vector<vector<int>>& graph, int start, unordered_map<int, int>& pre) {
    int n = graph.size();
    vector<int> dist(n, INT_MAX);
    vector<bool> visited(n, false);

    dist[start] = 0;

    for (int i = 0; i < n - 1; ++i) {
        int u = -1;
        // 找到起点到未访问的节点中距离最短的点
        for (int j = 0; j < n; ++j) {
            if (!visited[j] && (u == -1 || dist[j] < dist[u])) {
                u = j;
            }
        }

        visited[u] = true;

        // 更新起点到所有的点的距离,判断从点 u 到其它的点是否会更近
        for (int v = 0; v < n; ++v) {
            if (graph[u][v] != 0 && !visited[v]) {
                if (dist[v] > dist[u] + graph[u][v]) {
                    dist[v] = dist[u] + graph[u][v];
                    pre[v] = u; // 记录路径
                }

            }
        }
    }

    return dist;
}

// 获取起始节点到某个节点的路径
vector<int> getPath(int start, int end, const unordered_map<int, int>& predecessors) {
    vector<int> path;
    int current = end;
    while (current != start) {
        path.push_back(current);
        current = predecessors.at(current);
    }
    path.push_back(start);
    reverse(path.begin(), path.end());
    return path;
}

测试

int main() {
    vector<vector<int>> graph = {
        {0, 10, 3, 0},
        {10, 0, 0, 2},
        {3, 0, 0, 7},
        {0, 2, 7, 0}
    };

    int start = 0;
    unordered_map<int, int> pre;
    vector<int> shortestDist = dijkstra(graph, start, pre);

    // 起始节点到其它节点的最短路径大小
    for (unsigned i = 0; i < shortestDist.size(); ++i) {
        cout << "Vertex " << i << ": " << shortestDist[i] << endl;
    }

    // 打印起始节点到节点 3 的具体路径
    vector<int> path = getPath(start, 3, pre);
    for (auto it : path) {
        cout << it << " ";
    }
    cout << endl;

    return 0;
}

测试例子中表示的图为:
img

标签:dist,int,算法,最短,start,Dijkstra,vector,path,顶点
From: https://www.cnblogs.com/AngleLin/p/17580236.html

相关文章

  • 【Python】蒙特卡洛模拟 | PRNG 伪随机数发生器 | LCG 线性同余算法 | 马特赛特旋转算
    ......
  • 数组的常见操作及其算法
    一、数组的常见操作1、定义一个int类型的数组,里面包含10个元素,分别赋一些随机数,然后求出这10个元素的最大值、最小值、总和、平均值。注:随机数公式:(数据类型)(最小值+Math.random()*(最大值-最小值+1))publicstaticvoidtest01(){//创建一维数组int[]a......
  • HJ67 24点游戏算法
    1.题目读题 HJ67 24点游戏算法 考查点 2.解法思路 代码逻辑 具体实现importjava.util.Scanner;importjava.util.Arrays;publicclassHJ67{publicstaticvoidmain(String[]args){Scannersc=newScanner(System.in);whil......
  • 拆解雪花算法生成规则
    1介绍雪花算法(Snowflake)是一种生成分布式全局唯一ID的算法,生成的ID称为SnowflakeIDs或snowflakes。这种算法由Twitter创建,并用于推文的ID。目前仓储平台生成ID是用的雪花算法修改后的版本。雪花算法几个特性生成的ID分布式唯一和按照时间递增有序,毫秒数在高位,自增序列在低......
  • 基于协同过滤推荐算法-手语学习系统-项目实战
    我发布此篇文章有两个博客地址博客园:https://www.cnblogs.com/liuyangjava/p/17579030.htmlCSDN:https://blog.csdn.net/caleb_520/article/details/131899297?spm=1001.2014.3001.5502课程视频预览:【【毕设项目】基于协同过滤推荐算法-手语学习系统/2023年新课程】https://www......
  • Java3DES双倍长加密算法详解
     Java3DES双倍长加密算法是一种强大的加密算法,它可以保护我们的敏感数据不被未经授权的人访问。在本文中,我将详细介绍Java3DES双倍长加密算法的原理和使用方法。首先,让我们来了解一下Java3DES双倍长加密算法的原理。这种算法是基于DES(DataEncryptionStandard)算法的改进版本......
  • 左神算法-基础06-图
    左神算法-基础06-图图的存储方式邻接表邻接矩阵如何表达图?生成图?//图的节点publicclassNode{publicintvalue;//入度publicintin;//出度publicintout;publicArrayList<Node>nexts;publicArrayList<Edge>edges;......
  • 文心一言 VS 讯飞星火 VS chatgpt (65)-- 算法导论6.5 4题
    四、在MAX-HEAP-INSERT的第2行,为什么我们要先把关键字设为-∞,然后又将其增加到所需的值呢?文心一言:在MAX-HEAP-INSERT算法的第二行将关键字设为-∞,是为了保持堆的性质。堆是一种二叉树结构,其中每个节点的值都大于或等于其子节点的值。在MAX-HEAP-INSERT算法中,我们需要在......
  • 算法练习-day29
    贪心算法435.无重叠区间题意:给定一个区间的集合 intervals ,其中intervals[i]=[starti,endi] 。返回需要移除区间的最小数量,使剩余区间互不重叠 。实例:思路:本题和452.用最少数量的箭引爆气球做法非常类似,大家可以先看看我之前的文章。本题我们只需要统计重叠的区域,代码如......
  • 文心一言 VS 讯飞星火 VS chatgpt (65)-- 算法导论6.5 4题
    四、在MAX-HEAP-INSERT的第2行,为什么我们要先把关键字设为-∞,然后又将其增加到所需的值呢?文心一言:在MAX-HEAP-INSERT算法的第二行将关键字设为-∞,是为了保持堆的性质。堆是一种二叉树结构,其中每个节点的值都大于或等于其子节点的值。在MAX-HEAP-INSERT算法中,我们需要......