首页 > 编程语言 >dijkstra迪杰斯特拉算法(邻接表法)

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

时间:2024-05-17 19:19:23浏览次数:26  
标签:tmp dist int 迪杰 pos 表法 dijkstra 顶点 ear


算法简易过程:

迪杰斯特拉算法(朴素) 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)

代码如下:

//
// 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;
}


测试如下:



标签:tmp,dist,int,迪杰,pos,表法,dijkstra,顶点,ear
From: https://www.cnblogs.com/giperx/p/18198444

相关文章

  • 链式前向星+dijkstra
    #include<iostream>#include<vector>usingnamespacestd;constintN=1000;struct{intto;intw;intnext;}edge[N];inthead[N];voidadd_edge(intu,intv,intw){staticintcnt=0;edge[cnt].to=v;edge[cnt].w=......
  • Dijkstra(迪杰斯特拉)
    Dijkstra(迪杰斯特拉)算法简单版须知首先用几个数组表示需要的状态:dis[] 表示距离从初始点到对应点的距离,初始点置为0,其他置为无穷graph[][]邻接矩阵,记录两点间连线的权重,可以记录无向图和有向图check[]判断当前点是否被记录算法思路:假定a为起点,每......
  • Dijkstra
    非常经典的单源最短路算法。仅能用于正权图(边权可为\(0\))拥有朴素版\(O(n^2)\)和堆优化版\(O((n+m)\log{m})\)朴素版一般用邻接矩阵存图而优化版使用邻接表或者链式前向星,我常用链式前向星中心思想每次在没用过的点内找一个距离起点最近的点,用这个点对其他点进行松弛操......
  • 洛谷P1576最小花费(逆Dijkstra算法)
    背景:说实话,这题有点考建模思想,及对Dijkstra算法的理解思路:因为转账间有手续费,即有一定损失比例,故边权均小于1(比例来说),而边的路权值非和,而是积,故边权相当于负(因为每次乘会使dis[i]变小)而题目刚好求最大路,而边权又等价于全为负,不刚好是Dijkstra的逆运用吗?原理:等......
  • 力扣周赛394之别样DP + 别样Dijkstra
    别样DP题目链接https://leetcode.cn/problems/minimum-number-of-operations-to-satisfy-conditions/description/题目大意题目思路需要考虑m列每一列填什么的情况,因为最终每一列都是一样的考虑暴力,每一列都可以变成0-9有\(10^m\)次种情况,这必然是不可行的我们从前往......
  • Dijkstra算法
    单源最短路算法,不能处理负环,朴素版时间复杂度\(O(n^2)\),堆优化版时间复杂度\(O(nlogn)\)。Dijkstra算法的流程是:将所有的节点分为A、B的两个集合,一开始A集合中只有起点,其他的节点在B集合。定义B中的节点与A的距离:若邻接A中的结点,则距离为边权;反之距离无穷大。1.找到与A距离最小......
  • 最短路算法(Dijkstra + SPFA + Floyd)
    最短路算法(Dijkstra+SPFA+Floyd)Dijkstra算法1.算法基本介绍Dijkstra算法通常是求解单源最短路中最快的算法,但它无法处理存在负权边的情况(原因在正确性证明中)。Dijkstra本质上是一种贪心算法,通过不断调整每个点的“当前距离”最终得到最优结果,其实后面要讲到的几种算法也大......
  • 【科研相关知识】Dijkstra算法
    Dijkstra算法相关背景知识历史来源exampleDijkstra算法相关背景知识Dijkstra算法是解决图论中的最短路径问题而最短路径问题是在图中找到两个节点之间的最短路径在导航中确定路线最短,在网络中路由器使用Dijkstra算法确定最短路径和转发端口。最短路径算法有Dijkstra算......
  • 【学习笔记】dijkstra
    一、dijkstra1.定义&作用很简单。一个单源最短路算法。2.思想&实现我觉得sm的图已经够了。二、堆优化dijkstra1.先来认识一下proirity_queue2.如何使用proirity_queue对dijkstra优化?每一步,我们都需要找到\(d\)值最小的节点(即\(......
  • FFmpeg 7.0 “Dijkstra” 发布
    FFmpeg7.0“Dijkstra”发布来源:OSCHINA编辑: 白开水不加糖2024-04-0710:11:00 2国产数据库圈,为啥那么多水货?”FFmpeg7.0“Dijkstra”现已发布。此版本以荷兰计算机科学家EdsgerW.Dijkstra的名字命名,一些值得注意的变化包括原生VVC解码器(目前处于......