dijkstra迪杰斯特拉算法(邻接表法)

这篇具有很好参考价值的文章主要介绍了dijkstra迪杰斯特拉算法(邻接表法)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

算法简易过程:

  •  迪杰斯特拉算法(朴素) O(n^2)
    G={V,E}   V:点集合   E:边集合
    初始化时 令 S={某源点ear}, T=V-S= {其余顶点},T中顶点对应的距离(ear, Vi)值
              若存在,d(ear,Vi)为弧上的权值, dist【i】
              若不存在,d(ear,Vi)为 无穷大, dist【i】
     循环 n - 1次(n个点):
      1、从T中选取一个与S中顶点 有关联边 且 权值最小 的顶点 pos,加入到 S中
          (这里使用 flag数组来确定 是否属于 S集合,true为属于)
          (等于是 每次 选取 T点集中 dist最小的顶点 作为 pos 加入 S,既 flag置为 true)
      2、对其余T中顶点Vi的距离值进行修改:若加进 pos 作中间顶点,从ear -> pos -> Vi 的距离值缩短,则   更新dist
          (等于是 找出所有 pos -> Vi 边(有边连接的), 再加上原来源ear -> pos 权重,对比dist数组,如果权重更小则更新 => 更新dist最短路径长度,更新prev数组 更新前驱顶点为pos)

求单源有向图最短路径

使用邻接表法来存储顶点和边,录入有向图

(当然也可以无向图,不过录入时要录入两次,比如 a b 3        b a 3)

dijkstra迪杰斯特拉算法(邻接表法)

 代码如下:

//
// Created by Giperx on 2022/11/27.
//
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
#define INFINE 99999 // 定义最大
// 邻接表
struct ArcNode // 边信息
{
    int adjvex;//有向边的 目标顶点 下标(从1开始)
    int weight;//边的权值
    struct ArcNode *next; //邻接表,指向下一个邻接边信息
};

struct VertexNode // 顶点
{
    int vertex;//顶点下标(1 ~)
    ArcNode *firstedge;// 有向边信息节点指针(源为vertex)
};

struct AdjList // 图
{
    vector<VertexNode> adjlist;//顶点数组
    int vexnum;  //顶点数 
    int arcnum;  //边数
};

// 图的初始化
void createGraph(AdjList& G){
    cout << "输入顶点数 边数:" << endl;
    cin >> G.vexnum >> G.arcnum;
    // 初始化G的顶点数组
    for(int i = 0; i <= G.vexnum; i ++){ // 下标从1开始,所以初始化vexnum + 1个顶点(0无作用)
        VertexNode* tmp = new VertexNode;
        tmp->vertex = i, tmp->firstedge = nullptr;
        G.adjlist.emplace_back(*tmp);
    }
    //边信息
    // n1:源顶点     n2:目标顶点   we:权重(距离)
    int n1, n2, we;
    cout << "输入边信息:(a b we):" << endl; // a -> b  weight: we
    for(int i = 0; i < G.arcnum; i ++){
        cin >> n1 >> n2 >> we;
        // 初始化一个边节点,目标顶点为n2
        ArcNode* tmp = new ArcNode;
        tmp->adjvex = n2, tmp->weight = we;
        // 头插法 将边信息节点插入
        // 节约时间(尾插要一直遍历到尾部插入)
        tmp->next = G.adjlist[n1].firstedge;
        G.adjlist[n1].firstedge = tmp;
    }
}

// 获取两顶点之间权重weight(距离)
int getWeight(AdjList& G, int n1, int n2){
    if(n1 == n2) return 0;

    ArcNode* tmp = G.adjlist[n1].firstedge;
    while(tmp){
        if(tmp->adjvex == n2) return tmp->weight;
        tmp = tmp->next;
    }
    // 两点之间没有边,返回INFINE
    return INFINE;
}

// 迪杰斯特拉算法(朴素)
//G={V,E}   V:点集合   E:边集合
//初始化时 令 S={某源点ear}, T=V-S= {其余顶点},T中顶点对应的距离(ear, Vi)值
//          若存在,d(ear,Vi)为弧上的权值, dist【i】
//          若不存在,d(ear,Vi)为 无穷大, dist【i】
// 循环 n - 1次(n个点):
//  从T中选取一个与S中顶点 有关联边 且 权值最小 的顶点 pos,加入到 S中
//      (这里使用 flag数组来确定 是否属于 S集合,true为属于)
//      (等于是 每次 选取 T点集中 dist最小的顶点 作为 pos 加入 S,既 flag置为 true)
//  对其余T中顶点Vi的距离值进行修改:若加进 pos 作中间顶点,从ear -> pos -> Vi 的距离值缩短,则 更新dist
//      (等于是 找出所有 pos -> Vi 边(有边连接的), 再加上原来源ear -> pos 权重,
//      对比dist数组,如果权重更小则更新 => 更新dist最短路径长度,更新prev数组 更新前驱顶点为pos)
void Dijkstra(AdjList& G, int ear, vector<int>& prev, vector<int>& dist){
    // 初始化
    // flag数组记录 某点是否纳入已找到点集合
    // prev数组记录 前驱顶点下标
    // dist数组记录 从源顶点ear 到 i顶点的最短路径
    vector<bool> flag (G.adjlist.size() + 1, false);
    for(int i = 1; i <= G.vexnum; i ++) dist[i] = getWeight(G, ear, i), prev[i] = ear;
    flag[ear] = true, prev[ear] = 0;
    // 开始
    for(int i = 2; i <= G.vexnum; i ++){
        int pos = 1; // 未纳入的距离最小的顶点
        int weiMin = INFINE;
        for(int j = 1; j <= G.vexnum; j ++){
            if(!flag[j] && dist[j] < weiMin){
                weiMin = dist[j], pos = j;
            }
        }

        flag[pos] = true;
        for(int j = 1; j <= G.vexnum; j ++){
            if(!flag[j]){ // 未纳入点集中,找到pos到这些点的距离,与dist数组比较是否更新
                int tmpWei = getWeight(G, pos, j);
                if(tmpWei != INFINE) tmpWei = tmpWei + weiMin; // 两点距离应该为ear -> pos -> j
                if(tmpWei < dist[j]) {
                    dist[j] = tmpWei; // 距离更小则更新dist
                    prev[j] = pos; // 前顶点更新为pos
                }
            }
        }
    }

}

// 找路径
void pathDist(vector<int>& prev, vector<int>& dist, int ear){
    // prev数组中为1有2种情况(djikstra初始化过程的时候全赋值为1,后续一直未改变):
    // 1:从ear到 顶点 只有 ear -> 顶点 这一条路最短
    // 2:无法从ear到达的顶点
    for(int i = 1; i <= prev.size() - 1; i ++){
        stack<int> trace;
        if(ear == i) continue;
        cout << ear << " 到 " << i ;
        // 无连通
        if(dist[i] == INFINE) {
            cout << "无连通" << endl;
            continue;
        }
        cout << "最短距离:" << dist[i] << "  最短路径:";
        int tmp = i;
        while(tmp){ //  源顶点prev是0
            trace.push(tmp);
            tmp = prev[tmp];
        }
        // 开始出栈, 栈顶一定是ear源顶点
        cout << trace.top();
        trace.pop();
        while(!trace.empty()){
            cout << " -> " << trace.top();
            trace.pop();
        }
        cout << endl;
    }
}
int main(){
    AdjList G;
    createGraph(G);
    // prev数组记录 前驱顶点下标
    vector<int> prev (G.vexnum + 1, 0);
    // dist数组记录 从源顶点ear 到 i顶点的最短路径
    vector<int> dist (G.vexnum + 1, INFINE);
    // 从源点ear 出发,到达其余所有点的最短路径
    cout << "输入源顶点ear:";
    int ear;
    cin >> ear;
    Dijkstra(G, ear,prev, dist);
    pathDist(prev, dist, ear);
//    for(int &x:prev) cout << x << ' ';
//    for(int &x:dist) cout << x << ' ';
    return 0;
}

测试如下:

dijkstra迪杰斯特拉算法(邻接表法)

dijkstra迪杰斯特拉算法(邻接表法)dijkstra迪杰斯特拉算法(邻接表法) 文章来源地址https://www.toymoban.com/news/detail-465239.html

到了这里,关于dijkstra迪杰斯特拉算法(邻接表法)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 堆优化版迪杰斯特拉(Dijkstra)算法简单分析

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

    2023年04月08日
    浏览(52)
  • C语言 最短路径 迪杰斯特拉(Dijkstra)算法

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

    2024年02月03日
    浏览(44)
  • java实现迪杰斯特拉(Dijkstra)算法求解最短路问题

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

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

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

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

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

    2024年02月06日
    浏览(41)
  • 迪杰斯特拉(Dijkstra's )算法——解决带权有向无向图最短路径

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

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

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

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

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

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

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

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

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

    2024年02月10日
    浏览(50)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包