Java教程

最短路径算法整理

本文主要是介绍最短路径算法整理,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

最短路算法整理

这里主要介绍Floyd算法Dijkstra算法SPFA算法,由于Bellman-ford算法可优化为SPFA,故暂时忽略它。

1. Floyd算法

适用范围:无负权回路,边权可正负。

核心代码:

for (k = 1; k <= n; k++)
    for (i = 1; i <= n; i++)
        for (j = 1; j <= n; j++)
        {
            if (d[i][k] + d[k][j] < d[i][j])
            {
                d[i][j] = d[i][k] + d[k][j];
                path[i][j] = path[i][k];
            }
        }

时间复杂度:\(O(n^3)\)

优势:代码简单,用于稠密图效果更佳,求出所有点两两之间最短路。

缺点:时间复杂度较高。

2. Dijkstra算法

适用范围:不存在负权边,求单源最短路。

核心代码:

void Dijkstra(int u)
{
    memset(vis, 0, sizeof(vis));
    for (int i = 1; i <= n; i++)
    {
        dis[i] = map[u][i]; //初始化
    }
    vis[u] = 1;
    for (int t = 1; t < n; t++)
    {
        int minn = Inf, temp;
        for (int i = 1; i <= n; i++)
        {
            if (!vis[i] && dis[i] < minn)
            {
                minn = dis[i];
                temp = i;
            }
        }
        vis[temp] = 1;
        for (int i = 1; i <= n; i++)
        {
            if (map[temp][i] + dis[temp] < dis[i])
            {
                dis[i] = map[temp][i] + dis[temp];
            }
        }
    }
}

可加入堆优化:

#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
struct node
{
    int di;
    int xu;
    bool operator<(const node &rhs) const
    {
        return di > rhs.di;
    }
};
struct edge
{
    int to, nxt, v;
} e[200001];
int n, m, s;
int num_edge = 0, head[100001];
int dis[100001], v[100001];
priority_queue<node> Q;
void add(int pre, int to, int vi)
{
    e[++num_edge].nxt = head[pre];
    e[num_edge].to = to;
    e[num_edge].v = vi;
    head[pre] = num_edge;
}
int main()
{
    memset(dis, 0x3f, sizeof(dis));
    scanf("%d%d%d", &n, &m, &s);
    for (int i = 1; i <= m; i++)
    {
        int ui, vi, wi;
        scanf("%d%d%d", &ui, &vi, &wi);
        add(ui, vi, wi);
    }
    dis[s] = 0;
    node oop = {dis[s], s};
    Q.push(oop);
    while (!Q.empty())
    {
        node now = Q.top();
        Q.pop();
        int u = now.xu;
        if (vis[u] == 1)
            continue; //关键
        vis[u] = 1;
        for (int i = head[u]; i; i = e[i].nxt)
        {
            int gt = e[i].to, jz = e[i].v;
            if (dis[u] + jz < dis[gt])
            {
                dis[gt] = dis[u] + jz;
                node xt = {dis[gt], gt};
                Q.push(xt);
            }
        }
    }
    for (int i = 1; i <= n; i++)
    {
        cout << dis[i] << " ";
    }
}

时间复杂度:\(O(nlogn)\)

优点:快速,且不容易被卡

3. SPFA(Shortest Path Faster Algorithm)

适用范围:可含负权边单源最短路径,判负环

代码(包含判负环):

bool Spfa(int S)
{
    int t, temp;
    queue<int> Q;
    memset(visited, 0, sizeof(visited));
    memset(Dis, 0x3f, sizeof(Dis));
    memset(In, 0, sizeof(In));

    Q.push(S);
    visited[S] = true;
    Dis[S] = 0;

    while (!Q.empty())
    {
        t = Q.front();
        Q.pop();
        visited[t] = false;
        for (int i = p[t]; i; i = e[i].next)
        {
            temp = e[i].to;
            if (Dis[temp] > Dis[t] + e[i].w)
            {
                Dis[temp] = Dis[t] + e[i].w;
                if (!visited[temp])
                {
                    Q.push(temp);
                    visited[temp] = true;
                    if (++In[temp] > n) //In数组保存进队次数
                        return false;   //负环存在
                }
            }
        }
    }
    return true;    //负环不存在
}

时间复杂度:大约\(O(kE)\),其中\(k\)是常数,稀疏图中\(k<2\),最坏情况\(O(VE)\)。

优点:通常情况下较快。

缺点:容易被卡。

这篇关于最短路径算法整理的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!