Aczy156

Algorithm14.1 最短路

[TOC]

最短路

三大思路

  • Basic：Floyd
  • Greedy：Dijkstra
  • DP：Bellman-Ford、SPFA
Greedy DP Basic
代表方法 Dijkstra Bellman-Ford Floyd
数据结构 d[i]表示到起点的最小距离 d[i]表示到起点的最小距离 d[i][j]表示i、j两点之间的最小距离
思路
(V为点，E为边)		 1. 从所有其他点中找到距离起点最小的点argmin{d[i])}
2. 用距离起点最小的点和当前点来更新所有其他点
3. 复杂度$O(V^2)$		 1. 用所有其他点来更新当前点
2. 复杂度$O(V^2)$		 1. 选取起点i、中间点k、终点j三个点。
2. 用d[i][k]和d[k][j]来更新d[i][j]
3. 复杂度$O(V^3)$
优化思路 1. 寻找当前距离最小的点过程：优化从所有其他点中找到距离起点最小的点 => 利用优先队列/堆来不断选取距离最小的d
2. 刷新其他点距离的点集过程：将所有其他点缩小为相邻的点集 => 通过邻接表、链式前向星找相邻点		 SPFA
1. 优化所有其他点：将所有其他点缩小为相邻的点集 => 通过邻接表、链式前向星找相邻点
2. 优化当前点：维护队列，所有接触到的、没进队列的点都需要进队列被更新一次，从而逐步筛选出所有需要被更新的当前点。
优化方法详细 1. 从优先队列中取队首，也即d最小的点。
2. 从邻接表中找到这个点的所有邻接点，将值进行更新。
3. 复杂度$O(E\log{V})$		 1. 把当前点放在队列中（最初放的是起点s）
2. 从邻接表中找到这个点的所有邻接点，先松弛，后依据进入次数进入队列。
3. 复杂度$O(KE)$，其中K«E。
适用情况 1. 最短路且存在负权环：在筛选d的时候，负权环会让相同的最小的d不断变小
2. 最长路且存在正权环。		 对于重复进入队列点，即为存在负权环、正权环

博客引流：我的CSDN博客，关于最短路优化历程，洛谷P3379和P4779的优化历程

我的CSDN博客 洛谷P3371、P4779 最短路Dijikstra优化历程(邻接矩阵-＞邻接表-＞链式前向星-＞堆优化)

My-Template

邻接矩阵 or 链式前向星-普通

邻接矩阵 or 链式前向星-堆优化

struct nd {int pos, val;}
priority_queue<nd> pq;
int d[maxpoint], d1, d2; // 用于临时储存两个点到起点的距离，分别是u点到s点的距离以及v点到s点的距离
int vis[maxpoint];
int u, v; // 用于获取边的两个点的坐标，其中u是承接从优先队列中获得的点的位置，v是通过遍历邻接表获得的

void dijkstra(int s, int e) {
  for (int i = 1; i <= n; i++) d[i] = INF;
  dis[s] = 0;
  pq.push({s, dis[s]});
  while (!pq.empty()) {
    u = pq.top().pos, d1 = pq.top().val;pq.pop();
    if (!vis[u]) {
      vis[u] = 1;
      for (auto tm : G[u]) {
        v = tm.first, d2 = tm.second;
        if (d[v] < d1+d2) {
          d[v] = d1+d2;
          if (!vis[v]) pq.push({v, d[v]});
        }
      }
    }
  }
}

Dijkstra+邻接矩阵【用mp[maxn][maxn]二维矩阵储存】

#include <iostream>
using namespace std;
#define maxn 10010
typedef long long ll;
ll n, m, bg, dis[maxn], vis[maxn], mp[maxn][maxn], ta, tb, tc, tem, v;
const int INF = (1<<31)-1;

void dijkstra(){
    for (int i = 1; i <= n; ++i) dis[i] = mp[bg][i];
    vis[bg] = 1;
    for (int i = 1; i <= n; ++i) {
        tem = INF,v = 0;
        for (int j = 1; j <= n; ++j) if (!vis[j] && dis[j] <= tem) tem = dis[v=j];
        vis[v] = 1;
        for (int j = 1; j <= n; ++j) if (!vis[j] && dis[v]+mp[v][j] < dis[j]) dis[j] = dis[v]+mp[v][j];
    }
    for (int i = 1; i <= n; ++i) printf("%lld ", dis[i]);
}

int main() {
    scanf("%lld%lld%lld", &n, &m, &bg);
    for (int i = 0; i < m; ++i) {
        scanf("%lld%lld%lld", &ta, &tb, &tc);
        mp[ta][tb] = mp[tb][ta] = tc;
    }
    dijkstra();
    return 0;
}

Dijkstra+邻接表【结构体+用vector向量来进行储存】

数据结构：（详细的邻接表vector实现见 Algorithm14.0 图论 数据结构存储形式 ）

struct edge{int to, cost;};
vector<edge> gh[maxn];

https://www.luogu.com.cn/problem/P3371

题目大意：最短路模版

1、值的初始化=>dis数组除了dis[自身]全部初始化为INF。

2、过程：

遍历所有点
	遍历每个点的时候都重新遍历一边dis最短距离数组，从最短距离数组里选出最短的 值-tem 和 索引-v
	利用获取到的这个dis最短距离数组中的最小的，来更新邻接表gh[v]中的所有节点的距离，也就是gh[v]的所有to，更新方式是dis[to] = min(dis[to], dis[v]+cost)来更新

AC代码：

#include <iostream>
using namespace std;
#define maxn 50010
int n, m, bg, dis[maxn], vis[maxn], ta, tb, tc, tem, v;
#include <vector>
struct edge{
    int to, cost;
};
vector<edge> gh[maxn];
const int INF = 2147483647;

void dijkstra() {
    for (int i = 1; i <= n; ++i) dis[i] = INF;
    dis[bg] = 0;
    for (int i = 1; i <= n; ++i) {
        tem = INF, v = bg;
        for (int j = 1; j <= n; ++j) if (!vis[j] && dis[j] < tem) tem = dis[v=j];
        vis[v] = 1;
        for (int j = 0; j < gh[v].size(); ++j) {
            int tg = gh[v][j].to;
            if (!vis[tg] && dis[tg] > dis[v]+gh[v][j].cost) dis[tg]=dis[v]+gh[v][j].cost;
        }
    }
    for (int i = 1; i <= n; ++i) printf("%d ", dis[i]);
}

int main() {
    scanf("%d%d%d", &n, &m, &bg);
    for (int i = 0; i < m; ++i) {
        edge teme;
        scanf("%d%d%d", &ta, &teme.to, &teme.cost);
        gh[ta].push_back(teme);
    }
    dijkstra();
    return 0;
}

Dijkstra+链式前向星【结构体】

1、用链式前向星来存储图结构

2、跑裸的Dijkstra

#include <iostream>
using namespace std;
#define maxpoint 100010
#define maxedge 200010
#define INF 2147483647
int n, m, s, ta, tb, tc, dis[maxpoint], vis[maxpoint], v, tem=INF;
struct node {
    int to, next, cost;
}edge[maxedge]; int head[maxpoint], tot;

void addedge(int from, int to, int cost) {
    edge[++tot].to = to;
    edge[tot].next = head[from];
    edge[tot].cost = cost;
    head[from] = tot;
}

/*
 * 非堆优化
 */
void dijkstra() {
    for (int i = 1; i <= n; ++i) dis[i] = INF;
    dis[s] = 0;
    for (int i = 1; i <= n; ++i) {
        tem = INF;v = s;
        for (int j = 1; j <= n; ++j) if (!vis[j] && dis[j] < tem) tem = dis[v=j];
        vis[v] = 1;
        for (int j = head[v]; j; j=edge[j].next) {
            int to = edge[j].to;
            if (!vis[to] && dis[to] > dis[v]+edge[j].cost) dis[to] = dis[v]+edge[j].cost;
        }
    }
    for (int i = 1; i <= n; ++i) printf("%d ", dis[i]);
}

int main() {
    scanf("%d%d%d", &n, &m, &s);
    for (int i = 1; i <= m; ++i) {
        scanf("%d%d%d", &ta, &tb, &tc);
        addedge(ta, tb, tc);
    }
    dijkstra();
    return 0;
}

Dijkstra+链式前向星+多源最短路

在给dijkstra传参的时候把当前的源头给传进去，这样就可以进行不同源头的最短路计算了。

注意：多源最短路要进行多次的Dijkstra，所以在每次跑完了都要刷新vis/dis数组。

#include <iostream>
using namespace std;
#define maxpoint 1005
#define maxedge 100010
#define INF 2147483647
int n, m, ta, tb, tc, dis[maxpoint], vis[maxpoint], v, tem=INF, ans;
struct node {
    int to, next, cost;
}edge[maxedge];int head[maxpoint], tot;
#include <cstring>
#define cl(a, b) memset(a, b, sizeof(a))

void addedge(int from, int to, int cost) {
    edge[++tot].to = to;
    edge[tot].next = head[from];
    edge[tot].cost = cost;
    head[from] = tot;
}

void dijkstra(int s) {
    for (int i = 1; i <= n; ++i) dis[i] = INF;
    dis[s] = 0;
    vis[s] = 1;
    for (int i = 1; i <= n; ++i) {
        v=s;tem=INF;
        for (int j = 1; j <= n; ++j) if (!vis[j] && tem > dis[j]) tem = dis[v=j];
        vis[v] = 1;
        for (int j = head[v]; j; j=edge[j].next) {
            int to = edge[j].to;
            if (!vis[to] && dis[to] > dis[v]+edge[j].cost) dis[to] = dis[v]+edge[j].cost;
        }
    }
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; ++i) {
        scanf("%d%d%d", &ta, &tb, &tc);
        addedge(ta, tb, tc);
    }
    dijkstra(1);
    for (int i = 2; i <= n; ++i) ans += dis[i];
    for (int i = 2; i <= n; ++i) {
        cl(vis, 0);
        dijkstra(i);
        ans += dis[1];
    }
    printf("%d\n", ans);
    return 0;
}

Dijkstra+链式前向星+双向建图

【双向建图限制于有向图，无向图就没有双向建图一说了】

https://www.luogu.com.cn/problem/P1629

题目大意：从固定点去其他所有点，然后从所有去过的点返回。

1、反向建图：【类似于：并查集里边的反集=>通过把范围增大到二倍来实现反集；】

  • 声明的数据结构规模扩大2倍，edge[maxpoint<<1] head[maxponit<<1] dis[maxpoint<<1]
  • 反向建图的时候，在1~n的数组范围内正向建图，在n+1~n«1范围内反向建图
  • 在跑裸的dijkstra注意索引。正向是1～n，反向n+1~n«1
/*
 * 正反方向两面建图
 */
#include <iostream>
using namespace std;
#define maxpoint 1005
#define maxedge 100010
#define INF 2147483647
int n, m, ta, tb, tc, dis[maxpoint<<1], vis[maxpoint<<1], v, tem=INF, ans;
struct node {
    int to, next, cost;
}edge[maxedge<<1];int head[maxpoint<<1], tot;
#include <cstring>
#define cl(a, b) memset(a, b, sizeof(a))

void addedge(int from, int to, int cost) {
    edge[++tot].to = to;
    edge[tot].next = head[from];
    edge[tot].cost = cost;
    head[from] = tot;
}

void dijkstra(int s) {
    for (int i = 1; i <= n; ++i) dis[i] = INF;
    dis[s] = 0;
    vis[s] = 1;
    for (int i = 1; i <= n; ++i) {
        v=s;tem=INF;
        for (int j = 1; j <= n; ++j) if (!vis[j] && tem > dis[j]) tem = dis[v=j];
        vis[v] = 1;
        for (int j = head[v]; j; j=edge[j].next) {
            int to = edge[j].to;
            if (!vis[to] && dis[to] > dis[v]+edge[j].cost) dis[to] = dis[v]+edge[j].cost;
        }
    }
}

void reverse_dijkstra(int s) {
    for (int i = n+1; i <= n<<1; ++i) dis[i] = INF;
    dis[s] = 0;
    vis[s] = 1;
    for (int i = n+1; i <= n<<1; ++i) {
        v=s;tem=INF;
        for (int j = n+1; j <= n<<1; ++j) if (!vis[j] && tem > dis[j]) tem = dis[v=j];
        vis[v] = 1;
        for (int j = head[v]; j; j=edge[j].next) {
            int to = edge[j].to;
            if (!vis[to] && dis[to] > dis[v]+edge[j].cost) dis[to] = dis[v]+edge[j].cost;
        }
    }
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; ++i) {
        scanf("%d%d%d", &ta, &tb, &tc);
        addedge(ta, tb, tc);
        addedge(tb+n, ta+n, tc); // 反向建图
    }
    dijkstra(1);
    for (int i = 2; i <= n; ++i) ans += dis[i];
    cl(vis, 0);
    reverse_dijkstra(1+n);
    for (int i = 2+n; i <= n<<1; ++i) ans += dis[i];
    printf("%d\n", ans);
    return 0;
}

堆优化-结构体-Dijkstra提高效率

解决题目：数据增强的最短路，洛谷P4779

https://www.luogu.com.cn/problem/P4779

#include <iostream>
using namespace std;
#define maxpoint 100010
#define maxedge 200010
#define INF 2147483647
int n, m, s, ta, tb, tc, dis[maxpoint], vis[maxpoint], v, tem=INF;
struct node {
    int to, next, cost;
}edge[maxedge]; int head[maxpoint], tot;
#include <queue>
struct nd {
    int dis, pos;
    nd(int dis, int pos): dis(dis), pos(pos) {}
    bool operator < (const nd n) const {return dis > n.dis;}
};
priority_queue<nd> pq;

void addedge(int from, int to, int cost) {
    edge[++tot].to = to;
    edge[tot].next = head[from];
    edge[tot].cost = cost;
    head[from] = tot;
}

/*
 * 堆优化
 */
void dijkstra() {
    for (int i = 1; i <= n; ++i) dis[i] = INF;
    dis[s] = 0;
    pq.push(nd(0, s));
    while (!pq.empty()) {
        nd nw = pq.top();pq.pop();
        int from = nw.pos;
        if (!vis[from]) {
            vis[from] = 1;
            for (int i = head[from]; i; i=edge[i].next) {
                int to = edge[i].to;
                if (dis[to] > dis[from]+edge[i].cost) {
                    dis[to] = dis[from]+edge[i].cost;
                    if (!vis[to]) pq.push(nd(dis[to], to));
                }
            }
        }
    }
    for (int i = 1; i <= n; ++i) printf("%d ", dis[i]);
}

int main() {
    scanf("%d%d%d", &n, &m, &s);
    for (int i = 1; i <= m; ++i) {
        scanf("%d%d%d", &ta, &tb, &tc);
        addedge(ta, tb, tc);
    }
    dijkstra();
    return 0;
}

堆优化-pair进行绑定-Dijkstra提高效率

  • 利用make_pair来进行优化结构体，不要写一个新的结构体，也不需要重载运算符，直接利用pair，pair+priority_queue默认按照第一个元素进行排序
  • 注意：在声明优先队列的时候要声明小顶堆priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;
#include <queue>
priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;
void dijkstra(int s) {
    for (int i = 1; i <= n; ++i) d[i] = inf;
    d[s] = 0;
    pq.push(make_pair(0, s));
    while (!pq.empty()) {
        ll nw = pq.top().second;pq.pop();
        if (!vis[nw]) {
            vis[nw] = 1;
            for (int i = head[nw]; i; i=edges[i].nt) {
                int to = edges[i].to;
                if (d[to] > d[nw]+edges[i].val) {
                    d[to] = d[nw]+edges[i].val;
                    if (!vis[to]) pq.push(make_pair(d[to], to));
                }
            }
        }
    }
}

堆优化Dijkstra：

https://www.luogu.com.cn/problem/P1339

核心模块：数据结构和非堆优化的一样，都是dis[], tem, vis[], v,只不过在堆优化运用priority_queue优化的过程中，需要首先push进一个两端为bg-bg且长度为0的一条边

int dijkstra(int bg, int ed) {
    for (int i = 1; i <= n; ++i) dis[i] = inf;
    dis[bg] = 0;
    pq.push({bg, 0});
    while (!pq.empty()) {
        int nw = pq.top().idx;pq.pop();
        if (!vis[nw]) {
            vis[nw] = 1;
            for (int i = head[nw]; i; i=edges[i].next) {
                int to = edges[i].to;
                if (dis[to] > dis[nw]+edges[i].val) {
                    dis[to] = dis[nw]+edges[i].val;
                    if (!vis[to]) pq.push({to, dis[to]});
                }
            }
        }
    }
    return dis[ed];
}

SPFA 负权 & 无负圈

BF 负权 & 检测负圈

反向建图、堆优化

给出若干个点，得到每个点到指定点的最短来回距离

  • 所有点到指定点的来路距离=》单终点最短路 =》反向建图
  • 指定点往其他所有点的去的距离=》单源（头）最短路

注意：用堆优化的时候

  • 也是要两层的判断是否扫过了!vis
  • 初始化的时候也是要将d数组按照inf与0进行初始化。
Posted on Feb 1, 2021