Junie's Blog

最短路算法基础

全文共 928 字预计阅读 4 分钟

Dijkstra朴素 O(n2)O(n^2)

用途：

求解非负权图中单源最短路问题

思路：

维护一个已确定最短路径的顶点集合 SS 和一个存储源点到各个顶点的最短距离的数组 distdist 。

初始时， SS 只包含源点，distdist 中只有源点到自身的距离为 00 ，其他为无穷大。采用贪心策略，每次从未确定最短路径的顶点集合中选择距离源点最近的一个顶点，然后以该顶点为中介更新其他顶点的距离。

重复以下步骤直到 SS 包含所有顶点：

  • 从 distdist 中选出不在 SS 中且距离最小的顶点 uu，将 uu 加入 SS 。
  • 遍历 uu 的所有邻接顶点 vv ，如果dist[u] + w(u,v) < dist[v]，则更新dist[v] = dist[u] + w(u,v)，其中 w(u,v)w(u,v) 是边 (u,v)(u,v) 的权值。

代码：

int g[N][N], dist[N];
bool st[N];
 
int dijkstra()
{
    memset(dist,0x3f,sizeof dist);
    dist[1] = 0;
    for (int i = 0;i < n;i++)
    {
        int t = n + 1; //这样做是让dist[t]初始为无穷，方便找到要加入集合的那个点
        for (int j = 1;j <= n;j++)
            if (!st[j] && dist[t] > dist[j]) //找到在所有未访问过的节点中，dist值最小的节点t。这个节点是下一个要访问的节点。
                t = j;
        st[t] = 1;
        if (t == n) break; //如果t等于n，那么说明从1到n的最短路径已经找到了，循环可以结束
        for (int j = 1;j <= n;j++) 
            dist[j] = min(dist[j], dist[t] + g[t][j]); //更新所有未访问过的节点j的dist值
    }
    return dist[n];
}

Dijkstra堆优化 O(mlogn)O(mlogn)

思路

DijkstraDijkstra 算法的堆优化方法是利用堆（或优先队列）来存储和更新每个节点到源点的最短距离，从而减少寻找最小距离节点的时间复杂度。

  • 将未访问的节点放入一个堆中（通常使用小根堆）
  • 选取堆顶元素作为当前操作的节点，将其从堆中移除
  • 对于当前节点的每一个邻居节点，如果新的路径长度比原先的更短，就更新邻居节点的距离，然后将它插入堆中

代码

int e[N], ne[N], idx, h[N], w[N];
int n,m;
int dist[N];
bool st[N];
 
int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> q;
    q.push({0,1});
    while (!q.empty())
    {
        auto t = q.top();
        q.pop();
        int v = t.second;
        if (st[v]) continue; //已经在集合中就直接跳过
        st[v] = 1; //此时加入集合
        for (int i=h[v];~i;i=ne[i]) //邻接表遍历相邻结点
        {
            int j = e[i];
            if (dist[j] > dist[v] + w[i])
            {
                dist[j] = dist[v] + w[i]; //松弛
                q.push({dist[j], j}); //加入堆
            }
        }
    }
    return dist[n];
}

bellman-ford O(mn)O(mn)

用途

解决存在负权边的单源最短路径问题

基本思路

不断地松弛每条边来逐步缩小起点到各个节点的距离

给定一个加权有向图 G=(V,E)G=(V,E) ，其中 VV 表示顶点集合，E表示边集合，边 ee 的权重为 w(e)w(e) ，起点为 ss ，终点为 tt ，则 Bellman−FordBellman-Ford 算法的流程如下：

  1. 对于每个节点 i∈Vi∈V ，初始化距离数组 distance[i]distance[i] 为正无穷大，除了初始节点 ss ，这里将 distance[s]distance[s] 设置为 00 。

  2. 对于所有的节点 uu 和 vv ，如果存在一条从 uu 到 vv 的边 ee，更新distance[v] = min(distance[v], distance[u] + w(e))。

  3. 重复执行第2步，直到没有任何一条边可以使得 distancedistance 的值发生变化。

  4. 根据 distance[t]distance[t] 判断是否存在从 ss 到 tt 的路径，如果存在输出该路径，否则说明不存在从 ss 到 tt 的路径。

代码

struct
{
    int a,b,w;
}edge[M];
int n,m,k;
int dist[N], backup[N];
 
int bellman_ford()
{
    memset(dist,0x3f,sizeof dist);
    dist[1] = 0;
    for (int i=0;i<k;i++) //k是拓展的层数，如果要全图的距离，遍历n次即可
    {
        memcpy(backup, dist, sizeof dist); //每次只从上一层拓展，不然k没意义
        for (int j=0;j<m;j++)
        {
            int a = edge[j].a, b = edge[j].b, w = edge[j].w;
            dist[b] = min(dist[b], backup[a] + w);
        }
    }
    return dist[n];
}

spfa O(m)O(m) - O(mn)O(mn)

用途：

  • 解决存在负权边的单源最短路径问题，是Bellman-Ford算法的一种优化版本
  • 判断是否存在负环

基本思路

将起点放入队列中，然后不断从队列中取出节点，遍历其所有邻居节点，并尝试使用该节点更新邻居节点的距离值。如果某个邻居节点的距离值发生了变化，则将其加入队列中。这个过程会重复进行多次，直到队列为空为止。

代码

求最短路：

int e[N], ne[N], idx, h[N], w[N];
int dist[N];
int n,m;
bool st[N];
int q[N], tt,hh;
 
int spfa()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    q[tt++] = 1;
    st[1] = 1;
    while (hh <= tt)
    {
        int t = q[hh++];
        st[t] = 0;
        for (int i=h[t];~i;i=ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                if (!st[j])
                {
                    q[tt++] = j;
                    st[j] = 1;
                }
            }
        }
    }
    return dist[n];
}

判断负环：

int e[N], ne[N], idx, w[N], h[N];
int dist[N], q[N], tt , hh;
int n,m;
bool st[N];
int cnt[N];
 
bool spfa()
{
    memset(dist, 0x3f, sizeof dist);
    for (int i=1;i<=n;i++)
    {
        q[tt++] = i;
        st[i] = 1;
    }
    while (hh <= tt)
    {
        int t = q[hh++];
        st[t] = 0;
        for (int i=h[t];~i;i=ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                if (!st[j])
                {
                    q[tt++] = j;
                    st[j] = 1;
                    cnt[j] = cnt[t] + 1; //从源点到j经过的边数+1
                }
                if (cnt[j] >= n) return true; //边数超过n就代表存在负环
            }
        }
    }
    return false;
}

Floyd O(n3)O(n^3)

用途

解决任意两点间最短路径问题

基本思路

动态规划

给定一个加权有向图 G=(V,E)G=(V,E)，其中 VV 表示顶点集合， EE 表示边集合，边 ee 的权重为 w(e)w(e) ，则 FloydFloyd 算法的基本思路如下：

  • 对于任意两个节点 ii 和 jj ，初始化它们之间的距离 d[i][j]d[i][j] 为 ii 到 jj 的直接距离，如果不存在直接边，则距离为正无穷大。

  • 对于每个节点 k∈Vk∈V ，尝试使用 kk 节点作为中介点来缩短 ii 到 jj 的距离，即d[i][j] = min(d[i][j], d[i][k] + d[k][j])。

重复执行第2步，直到所有节点之间的距离都被计算出来。

代码

int d[N][N];
 
int floyd()
{
    for (int k=1;k<=n;k++)
        for (int i=1;i<=n;i++)
            for (int j=1;j<=n;j++)
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}

评论