单源最短路模板

单源最短路常用模板

SPFA

朴素版

//Bellman-Ford 队列优化
//SPAF
#include<iostream>
#include<vector>
#include<queue>
using namespace std;

int main()
{
    int n, m, s;
    const int inf = 99999999;
    cin >> n >> m >> s;
    vector<int> a(m + 1), b(m + 1), c(m + 1), first(n + 1, -1), next(m + 1), dis(n + 1, inf);
    vector<bool> book(n + 1, false);
    queue<int> q;

    dis[s] = 0;

    for (int i = 1; i <= m; ++i)
    {
        cin >> a[i] >> b[i] >> c[i];
        next[i] = first[a[i]];
        first[a[i]] = i;
    }

    q.emplace(s);
    book[s] = true;

    while (!q.empty())
    {
        int k = first[q.front()];
        while (k != -1)
        {
            if (dis[b[k]] > dis[a[k]] + c[k])
            {
                dis[b[k]] = dis[a[k]] + c[k];
                if (book[b[k]] == false)
                {
                    q.emplace(b[k]);
                    book[b[k]] = true;
                }
            }
            k = next[k];
        }
        book[q.front()] = false;
        q.pop();
    }

    for (int i = 1; i <= n; ++i)
        cout << dis[i] << " ";

    return 0;
}

SPFA + 链式前向星

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
struct EDGE
{
    int to;
    int next;
    int w;
}edge[101];
int head[101], cnt = 1;
int  n, m;
int  dis[101];
bool vis[101];
const int inf = 99999;
queue<int> q;

void add(int a, int b, int w)
{
    edge[cnt].w = w;
    edge[cnt].to = b;
    edge[cnt].next = head[a];
    head[a] = cnt++;
}
void spfa(int x)
{
    //初始化dis数组
    fill(dis, dis + 101, inf);
    //将起点放入队列用起点松弛
    q.push(x);
    dis[x] = 0;
    vis[x] = 1;
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        vis[u] = 0;
        //松弛操作
        for (int i = head[u]; i != 0; i = edge[i].next)
        {
            int v = edge[i].to;
            if (dis[v] > dis[u] + edge[i].w) {
                dis[v] = dis[u] + edge[i].w;
                //如果松弛成功且这个点又没有再队列中就把它加入队列尾部
                if (vis[v] == 0) {
                    q.push(v);
                    vis[v] = 1;
                }
            }
        }
    }
}
int main()
{
    cin >> n >> m;
    int a, b, c;
    for (int i = 0; i < m; i++)
    {
        cin >> a >> b >> c;
        add(a, b, c);
        add(b, a, c);
    }
    cout << "输入访问点:";
    int x; cin >> x;
    spfa(x);
    for (int i = 1; i <= n; i++)
        cout << dis[i] << " ";
    system("pause");
    return 0;
}

Digkstra

Dijkstra + 链式前向星

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n, A, B;
int dis[10001];
bool vis[10001];
const int inf = 999999999;
//链式前向星
struct EDGE
{
    int w;
    int to;
    int next;
}edge[10001];
int head[10001];
int cnt = 1;
void add(int a, int b, int w)
{
    edge[cnt].to = b;
    edge[cnt].w = w;
    edge[cnt].next = head[a];
    head[a] = cnt++;
}
void Dijkstra(int node)
{
    fill(dis, dis + 10001, inf);
    dis[node] = 0;
    for (int i = 1; i <= n - 1; i++)
    {
        int u = -1,minn = inf;
        for (int j = 1; j <= n; j++)
        {
            if (vis[j] == false && dis[j] < minn)
            {
                u = j;
                minn = dis[j];
            }
        }
        if (u == -1)break;
        vis[u] = 1;
        for (int i =head[u]; i!= 0; i = edge[i].next)
        {
            int v = edge[i].to;
            if (dis[v] > dis[u] + edge[i].w)
                dis[v] = dis[u] + edge[i].w;
        }
    }
}
int main()
{
    cin >> n >> A >> B;
    fill(head, head + 10001, 0);
    int x = 1;
    while (x <= n)
    {
        int k, a;
        cin >> k;
        for (int i = 0; i < k; i++)
        {
            cin >> a;
            if(i == 0)
            add(x, a, 0);
            else{
            add(x, a, 1);
            }
        }
        x++;
    }
    Dijkstra(A);
    if (dis[B] < inf)
        cout << dis[B] << endl;
    else
        cout << "-1" << endl;
    system("pause");
    return 0;
}

Dijkstra + 堆优化

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <queue>
using namespace std;
const int N = 100010;
const int M = 500010;

// 堆优化版本 O((m + n)logn) 
// 不能处理负边权
struct edge
{
    int to, dis , next;
}e[M];
int head[N], dis[N], cnt, n , m ,s;
bool vis[N];

void add(int a,int b,int v)
{
    cnt++;
    e[cnt].dis = v;
    e[cnt].to = b;
    e[cnt].next = head[a];
    head[a] = cnt;
}
struct node
{
    int dis;
    int pos;
    bool operator <(const node &x)const{
        return x.dis < dis;
    }
};

priority_queue<node> q;


void dijkstra()
{
    dis[s] = 0;
    q.push((node){0,s});
    while(!q.empty())
    {
        node tmp = q.top();
        q.pop();
        int x = tmp.pos;
        if(vis[x])continue;
        vis[x] = 1;
        for(int i = head[x];i  ;i = e[i].next)
        {
            int y = e[i].to;
            if(dis[y] > dis[x] + e[i].dis)
            {
                dis[y] = dis[x] + e[i].dis;
                if(!vis[y])
                {
                    q.push((node){dis[y],y});
                }
            }
        }
    }
}
int main()
{
    cin >> n >> m >> s;
    for(int i = 1;i <= n ;i ++)dis[i] = 0x7fffffff;
    for(register int i = 0;i < m ; ++i)
    {
        register int a , b , c;
        scanf("%d %d %d",&a , &b ,&c);
        add(a , b ,c);
    }
    dijkstra();
    for(int i = 1;i <= n ;i ++)
    {
        printf("%d ", dis[i]);
    }
    return 0;
}

Bellman-ford 算法

//Bellman-Ford 普通算法 
#include<iostream>
#include<vector>
using namespace std;
int main()
{
    int n, m, s;
    cin >> n >> m >> s;
    const int inf = 99999;
    vector<int> a(m), b(m), c(m), dis(n, inf);
    for (int i = 0; i < m; ++i)
        cin >> a[i] >> b[i] >> c[i];
    dis[s - 1] = 0;

    //Bellman-Ford 算法核心内容
    bool check;
    for (int k = 0; k < n - 1; ++k)
    {
        check = false;
        for (int i = 0; i < m; ++i)
            if (dis[b[i] - 1] > dis[a[i] - 1] + c[i])
            {
                dis[b[i] - 1] = dis[a[i] - 1] + c[i];
                check = true;
            }
        if (!check)
            break;
    }

    //Bellman-Ford 算法也可用于判断图中是否含有负权回路
    for (int i = 0; i < m; ++i)
        if (dis[b[i] - 1] > dis[a[i] - 1] + c[i])
        {
            cout << "此图中含有负权回路" << endl;
            break;
        }

    for (auto i : dis)
        cout << i << " ";
    return 0;
}

原文链接: https://www.cnblogs.com/wlw-x/p/12628246.html

欢迎关注

微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍;

也有高质量的技术群,里面有嵌入式、搜广推等BAT大佬

    单源最短路模板

原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/339751

非原创文章文中已经注明原地址,如有侵权,联系删除

关注公众号【高性能架构探索】,第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处!

(0)
上一篇 2023年3月2日 上午12:16
下一篇 2023年3月2日 上午12:16

相关推荐