Shortest Path

A Dijkstra (SSSP)

在联通带权图中寻找顶点a到顶点z的最短路径的长度。边$(i,j)$的权值$w(i,j)>0$，且顶点的标注为$L(x)$，结束时，$L(z)$是从$a$到$z$的最短路径的长度。
$$BFS实质上是dijkstra的弱化版，即无权图$$

Code

Pseudo Code

dijkstra(w,a,z,L){
L(a)=0
for all vertices x!=a
L(x)=inf
T=set of all vertices
// 临时标注的顶点集合，从a到有最短路径的顶点集合
// 没找到
while(z属于T){
choose v属于T with minimum L(v)
T=T-{v}
for each x属于T adjacent to v
L(x)=min{L(x),L(v)+w(v,x)}
}
}

Adjacency Matrix & Force

$$time:O(V^2)$$
$$space:O(V^2)$$

// Initialization
const int maxn = 1e4 + 7;
const int inf = 1 << 31 - 1;
int AdjMatrix[maxn][maxn];
bool vis[maxn];
int dis[maxn];

void dijkstra_AdjMatrix(){
for (int i = 0; i < maxn; i++){
dis[i] = inf;
// 初始化到i点的最短路
}
memset(vis, 0, sizeof vis);
dis[1] = 0;
// 到起始点的距离，可以改为起始点下标
for (int i = 1; i<n; i++){
int x = 0;
// 当前dis最小的点
for (int j = 1; j <= n; j++){
if(!vis[j] && (x==0 || dis[j]<dis[x]))
// 在T集合中，且自起始点路长最短
x = j;
}
vis[x] = 1;
// 该点被从T集合中剔除
for (int j = 1; j<=n; j++){
dis[j] = min(dis[j], dis[x] + AdjMatrix[x][j]);
// 松弛操作 L(x)=min{L(x),L(v)+w(v,x)}
}
}
}

Priority Queue & Adjacency List & Count

$$time:O((V+E)\lg V)$$
$$space:O(V+E)$$

// Initialization
const int maxn = 1e4 + 7;
const int tempp = (1 << 31) - 1;
// 注意左移符号优先级低于+-号
const int INF = 2147483647;
int n = 0;
// n为点的数目，m为边的数目
// Dijkstra
// 单源最短路
// 邻接表
// 优先队列
// 边权非负
// O(mlog(m))

struct edge {
// 边
int v, w;
};
struct node {
// 加入优先队列的节点
int dis, u;
bool operator>(const node& a) const { return dis > a.dis; }
// 重载运算符，用于实现优先队列参数
};
vector<edge> e[maxn];
// vector邻接表
int dis[maxn], vis[maxn], cnt[maxn];
// dis为出发点到i节点最短距离，vis为是否松弛了该节点, cnt为最短路计数
void dijkstra(int n, int s){
priority_queue<node, vector<node>, greater<node>> q;
for (int i = 0; i<maxn; i++){
dis[i] = INF;
vis[i] = 0;
}
dis[s] = 0;
cnt[s] = 1;
q.push({0, s});
while(!q.empty()){
int u = q.top().u;
q.pop();
if(vis[u])
continue;
vis[u] = 1;
for(auto ed:e[u]){
int v = ed.v, w = ed.w;
if(dis[v]>dis[u]+w){
dis[v] = dis[u] + w;
q.push({dis[v], v});
cnt[v] = cnt[u];
}
else if(dis[v]==dis[u]+w){
//*count the shortest path
cnt[v] += cnt[u];
//*put it in relaxation
cnt[v] %= mod;
//*
}
//*
}
}
}

signed main(){
int m;
int s;
cin >> n >> m >> s;
// 节点数，边数，起始节点编号
int a, b, diss;
for (int i = 0; i < m; i++){
cin >> a >> b >> diss;
e[a].push_back({b, diss});
}
dijkstra(n, s);
for (int i = 1; i <= n; i++){
cout << dis[i] << " ";
}
return 0;
}

B Bellman-Ford (negative loop && SSSP)

Code

$$time:O(E\ast V)$$
$$space:O(V+E)$$

// Initialization
const int INF = 1e6;
const int NUM = 105;
struct edge{
int u, v, w;
// u: source, v: sink, w: weight
} e[10005];
int n, m, cnt;
int pre[NUM];
// 最短路上的前驱节点: pre[x] = y

void print_path(int s, int t){
if(s==t){
printf("%d", s);
return;
}
print_path(s, pre[t]);
printf("%d", t);
}
void Bellman(){
int s = 1;
// source
int d[NUM];
// distance
for (int i = 1; i <= n; i++){
d[i] = INF;
}
d[s] = 0;
for (int k = 1; k <= n; k++){
for (int i = 0; i < cnt; i++){
int x = e[i].u, y = e[i].v;
if(d[x]>d[y]+e[i].w){
d[x] = d[y] + e[i].w;
pre[x] = y;
// if needed
}
}
}
}

Detection of Negative Ring

void bellman(){
int d[NUM];
for (int i = 2; i <= n; i++){
d[i] = INF;
}
d[1] = 0;
int k = 0;
// how many rounds we have operated
bool update = true;
while(update){
k++;
update = false;
if(k>n){
printf("负环");
return;
}
for (int i = 0; i < cnt; i++){
int x = e[i].u, y = e[i].v;
if(d[x]>d[y]+e[i].w){
update = true;
d[x] = d[y] + e[i].w;
}
}
}
}

C SPFA (SSSP & negative loop)

Code

$$\ast \ast unstable\ast \ast$$
$$time:O(k\ast V)-for-sparse-graph$$
$$time:O(E\ast V)-for-dense-graph$$
$$space:O(V+E)$$

Adjacency List Version

// Initializaiton
const int INF = 0x3f3f3f3f;
const int NUM = 105;
struct edge{
int from, to, w;
edge(int a, int b, int c){
from = a;
to = b;
w = c;
}
};
vector<edge> e[NUM];
int n, m;
int pre[NUM];
void print_path(int s, int t){
if(s==t){
printf("%d", s);
return;
}
print_path(s, pre[t]);
printf("%d", t);
}

int spfa(int s){
int dis[NUM];
// distance
bool inq[NUM];
// whether in queue
int Neg[NUM];
// detect negative loop
memset(Neg, 0, sizeof Neg);
Neg[s] = 1;
for (int i = 1; i<=n; i++){
dis[i] = INF;
inq[i] = false;
}
dis[s] = 0;
queue<int> Q;
Q.push(s);
inq[s] = true;
while(!Q.empty()){
int u = Q.front();
Q.pop();
inq[u] = false;
for (int i = 0; i < e[u].size(); i++){
int v = e[u][i].to, w = e[u][i].w;
if(dis[u]+w<dis[v]){
dis[v] = dis[u] + w;
pre[v] = u;
if(!inq[v]){
inq[v] = true;
Q.push(v);
Neg[v]++;
if(Neg[v]>n){
printf("负环");
return -1;
}
}
}
}
}
}

Chained Forward Star Version

// Initialization
const int INF = INT_MAX / 10;
const int NUM = 1e6 + 5;
struct Edge{
int to, next, w;
} edge[NUM];
int n, m, cnt;
int head[NUM];
int dis[NUM];
// distance
bool inq[NUM];
// true -> in queue
int Neg[NUM];
// detect negative looooop
int pre[NUM];
// predecessor node

// assistance function
void print_path(int s, int t){}
// same as before
void init(){
for (int i = 0; i < NUM; i++){
edge[i].next = -1;
head[i] = -1;
}
cnt = 0;
}
void addedge(int u, int v, int w){
edge[cnt].to = v;
edge[cnt].w = w;
edge[cnt].next = head[u];
head[u] = cnt++;
}

int spfa(int s){
memset(Neg, 0, sizeof Neg);
Neg[s] = 1;
// why
for (int i = 1; i <= n; i++){
dis[i] = INF;
inq[i] = false;
}
dis[s] = 0;
queue<int> q;
q.push(s);
inq[s] = true;
// source point in queue
while(!q.empty()){
int u = q.front();
q.pop();
inq[u] = false;
for (int i = head[u]; ~i; i = edge[i].next){
// i!=-1
int v = edge[i].to, w = edge[i].w;
if(dis[u]+w<dis[u]){
dis[v] = dis[u] + w;
pre[v] = u;
if(!inq[v]){
inq[v] = true;
q.push(v);
Neg[v]++;
if(Neg[v]>n)
return -1;
// negative loop
}
}
}
}
}

最后

以上就是乐观棒球为你收集整理的最短路模板 （Dijkstra + Bellman-Ford + SPFA）（邻接表 + 链式前向星）（最短路计数+打印最短路+判断负环）（时间+空间复杂度）Shortest Path的全部内容，希望文章能够帮你解决最短路模板 （Dijkstra + Bellman-Ford + SPFA）（邻接表 + 链式前向星）（最短路计数+打印最短路+判断负环）（时间+空间复杂度）Shortest Path所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。