最短路学习笔记

qiutianqwq · 2022-08-10 19:10:12 · 个人记录

目录

• 概念讲解
• Floyed-Warshall + 判断连通性
• Dijkstra + 优先队列优化
• Bellman-Ford
• SPFA

概念

字面意义，最短路径就是连接两点的这些路径中最短的一条。

Floyed-Warshall

Floyed-Warshall（弗洛伊德）算法，是最简单的最短路算法，可以计算图中任意两点的最短路。

复杂度: O(n^{3}) 。

思想：枚举 i, j 再在外层枚举一个中间点 k 来松弛，如果原先 i 到 k 到距离加上 k 到 j 到距离小于原先 i 到 j 的距离，就更新 i 到 j 距离的最小值。

初始化：若点 u,v 间有一条权值为 w 的边，dis[u][v] = w，否则 dis[u][v] = \infty 。

for (int k = 1; k <= n; k++) //中间点 
{
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (dis[i][k] == INT_MAX || dis[k][j] == INT_MAX)   continue; //i、k和k、j是否有最小值 
            dis[i][j] = min (dis[i][j], dis[i][k] + dis[k][j]); //更新 
        }
    }
}

练习：P1339 [USACO09OCT]Heat Wave G

判断连通性

和求最短路相似

初始化：若点 u, v 间有边， dis[u][v] = true，否则 dis[u][v] = false。

for (int k = 1; k <= n; k++)
{
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            dis[i][j] = (dis[i][j] || (dis[i][k] && dis[k][j]));
        }
    }
}

Floyed适用于负边权

Dijkstra

Dijkstra （迪杰斯特拉算法）算法，是单源最短路算法，可以计算图中任意点到源点的最短路。

复杂度: O(n^{2}) 。

思想：主要是贪心思想，每次寻找一个未被访问的一个点 u 使得 dis[u] 是最小的，将 u 标记被访问，再枚举更新与 u 相连的最短路径。

初始化：设起点为 s,dis[s] = 0 。

void dijkstra ()
{
    for (int i = 1; i <= n; i++)    dis[i] = INT_MAX; //初始化 
    dis[s] = 0;
    for (int i = 1; i <= n; i++)
    {
        //找最小值、 最小值编号 
        int minn = INT_MAX, minj = -1;
        for (int j = 1; j <= n; j++)
        {
            if (minn > dis[j] && !vis[j])
            {
                minn = dis[j];
                minj = j;
            }
        }
        if (minj == -1) break;
        //标记 
        vis[minj] = true;
        //更新 
        for (int j = 1; j <= n; j++)
        {
            if (vis[j])                 continue;
            if (mp[minj][j] == INT_MAX) continue;
            dis[j] = min (dis[j], dis[minj] + mp[minj][j]);
        }
    }
    return ;
}

练习：P3371 【模板】单源最短路径（弱化版）

你会惊奇地发现这个复杂度太高了，需要优化。

Dijkstra + 堆优化

基本思想是一样的，用优先队列把找找最小值、 最小值编号优化了。

复杂度：O(m + nlogn)。

void dijkstra ()
{
    for (int i = 1; i <= n; i++)    dis[i] = INF; //初始化 
    dis[s] = 0;
    q.push (Node {0, s});
    while (!q.empty ())
    {
        Node cur = q.top ();
        q.pop ();
        if (vis[cur.x]) continue;
        //标记 
        vis[cur.x] = true;
        for (int j = head[cur.x]; j != -1; j = edge[j].next)
        {
            int to = edge[j].to;
            if (vis[to])    continue;
            //更新 
            if (dis[to] > dis[cur.x] + edge[j].dis)
            {
                dis[to] = dis[cur.x] + edge[j].dis;
                q.push (Node {dis[to], to});
            }
        }
    }
    return ;
}

练习：P4779 【模板】单源最短路径（标准版）

Dijkstar不适用存在负边权的情况。

Bellman-Ford

简称 Ford(福特)算法，也是单源最短路算法。

复杂度： O(NE) , N 是点的数量， E 是边的数量。

每次遍历边， 遍历 (n - 1) 次，每次标记与更新与黑点相连的白点。

建议用边集数组。

初始化：设起点为 s,dis[s] = 0。

void ford ()
{
    for (int i = 1; i <= n; i++)    dis[i] = INF; //初始化 
    dis[s] = 0;
    for (int i = 1; i < n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            int u = edge[j].u, v = edge[j].v; //u、v是这条边连接的两个点 
            //更新 
            if (dis[v] == INF)  continue;
            dis[v] = min (dis[v], dis[u] + edge[j].w);
        }
    } 
    return ;
}

图解：

1. 初始化了 dis[1] = 0。