做网站用哪个开发工具好,松江公司做网站,wap建站程序哪个好,电商手机网站建设不存在负权边#xff1a;
1.朴素dijkstra算法
原题#xff1a; 思路#xff1a;#xff08;依然是贪心的思想#xff09;
1.初始化距离#xff1a;dis[1]0#xff0c;dis[i]INF#xff08;正无穷#xff09;
2.循环n次#xff1a; 找到当前不在s中的dis最小的点
1.朴素dijkstra算法
原题 思路依然是贪心的思想
1.初始化距离dis[1]0dis[i]INF正无穷
2.循环n次 找到当前不在s中的dis最小的点s表示已经确定最短距离的点可以开一个st数组表示 假设找到了t这个点用这个点更新其他所有点的最短距离 if dis[x]dis[t]wi这里wi表示边权 实例演示 代码如下
一些注意细节用//表示
c版本
#include iostream
#include cstringusing namespace std;
const int N510;
int q[N][N];
int dis[N];
int n,m;
bool st[N];
int dijkstra(){memset(dis,0x3f,sizeof dis);dis[1]0;for(int i0;in-1;i){int t-1;for(int j1;jn;j){if(!st[j](t-1||dis[t]dis[j])){
//这里t-1其实代表是第一次进入更新t的值而后面才开始比较tj;}}for(int j1;jn;j){dis[j]min(dis[j],dis[t]q[t][j]);}st[t]1;}if(dis[n]0x3f3f3f3f) return -1;return dis[n];
}int main(){cinnm;memset(q,0x3f,sizeof q);while(m--){int x,y,z;cinxyz;q[x][y]min(q[x][y],z);}coutdijkstra() ;return 0;
}
C
#include stdio.h
#include string.h#define N 510int q[N][N];
int dis[N];
int n, m;
int st[N];int min(int a, int b) {return a b ? a : b;
}int dijkstra() {memset(dis, 0x3f, sizeof(dis));dis[1] 0;for (int i 0; i n - 1; i) {int t -1;for (int j 1; j n; j) {if (!st[j] (t -1 || dis[t] dis[j])) {t j;}}for (int j 1; j n; j) {dis[j] min(dis[j], dis[t] q[t][j]);}st[t] 1;}if (dis[n] 0x3f3f3f3f) return -1;return dis[n];
}int main() {scanf(%d %d, n, m);memset(q, 0x3f, sizeof(q));while (m--) {int x, y, z;scanf(%d %d %d, x, y, z);q[x][y] min(q[x][y], z);}printf(%d , dijkstra());return 0;
}python:
import sys N 510
q [[float(inf)] * N for _ in range(N)] # 初始化邻接矩阵
dis [float(inf)] * N # 初始化距离数组
st [False] * N # 初始化标记数组 n, m map(int, input().split()) # 读取节点数和边数 # 读取边的信息
for _ in range(m): x, y, z map(int, input().split()) q[x - 1][y - 1] min(q[x - 1][y - 1], z) # 注意索引从0开始 def dijkstra(): dis[0] 0 # 起始节点距离设为0 for _ in range(n - 1): t -1 for j in range(n): if not st[j] and (t -1 or dis[j] dis[t]): t j for j in range(n): if q[t][j] ! float(inf): dis[j] min(dis[j], dis[t] q[t][j]) st[t] True if dis[n - 1] float(inf): return -1 return dis[n - 1] print(dijkstra()) Go
package main import ( bufio fmt math os strconv strings
) const N 510 var ( q [N][N]int dis [N]int n int m int st make([]bool, N)
) func min(a, b int) int { if a b { return a } return b
} func dijkstra() int { for i : range dis { dis[i] math.MaxInt32 } dis[0] 0 // 注意Go的数组索引从0开始 for i : 0; i n; i { t : -1 for j : 0; j n; j { if !st[j] (t -1 || dis[j] dis[t]) { t j } } for j : 0; j n; j { if q[t][j] ! math.MaxInt32 { dis[j] min(dis[j], dis[t]q[t][j]) } } st[t] true } if dis[n-1] math.MaxInt32 { return -1 // 如果没有路径到达节点n-1 } return dis[n-1]
} func main() { scanner : bufio.NewScanner(os.Stdin) fmt.Scanln(n, m) for i : range q { for j : range q[i] { q[i][j] math.MaxInt32 } } for m 0 { m-- scanner.Scan() line : scanner.Text() fields : strings.Fields(line) x, _ : strconv.Atoi(fields[0]) y, _ : strconv.Atoi(fields[1]) z, _ : strconv.Atoi(fields[2]) x-- // 转换为Go的索引 y-- q[x][y] min(q[x][y], z) } fmt.Println(dijkstra())
}
这里储存方式用邻接矩阵主要是因为用于稠密图。图中可能存在重边和自环但所有边权均为正值。算法复杂度
2.堆优化的dijkstra 我们思考一下上述步骤在哪里可以优化找到当前不在s中的dis最小的点我们可以用堆进行优化优化后复杂度为堆优化手写堆和优先队列但是其实在dijkstra中不需要手写堆两个复杂度差不多不如用优先队列方便。并且此时为稀疏图用邻接表更好。 我们用邻接表现在只需要遍历邻接表中头元素连接的进行更改每一次取出队列中的最小值即可
C
#include iostream
#include cstring
#include queue
using namespace std;
const int N 1e6 10;//注意开两倍大小
int h[N], w[N], e[N], ne[N], idx;
int n,m;
int dis[N];
bool st[N];
typedef pairint,int PII;
priority_queuePII,vectorPII,greaterPII p;
void add(int a, int b, int c)//模板记下来就好了
{e[idx] b, w[idx] c, ne[idx] h[a], h[a] idx ;
}
int dijkstra(){memset(dis,0x3f,sizeof dis);dis[1]0;p.push({0,1});while(p.size()){auto tp.top();p.pop();int vert.second;if(st[ver]) continue;//判断是否之前更新过了st[ver]1;for(int ih[ver];i!-1;ine[i]){int je[i];if(dis[j]dis[ver]w[i]){dis[j]dis[ver]w[i];p.push({dis[j],j});}}}if(dis[n]0x3f3f3f3f) return -1;return dis[n];
}int main(){cinnm;memset(h, -1, sizeof h);//邻接表记得初始化头结点while (m -- ){int a, b, c;scanf(%d%d%d, a, b, c);add(a, b, c);}coutdijkstra() ;return 0;
}
python:
import heapqN 1000010
h [-1] * N
w [0] * N
e [0] * N
ne [0] * N
idx 0
n, m map(int, input().split())
dis [float(inf)] * N
st [False] * N
p []def add(a, b, c):global idxe[idx] bw[idx] cne[idx] h[a]h[a] idxidx 1def dijkstra():global disdis[1] 0heapq.heappush(p, (0, 1))while p:d, ver heapq.heappop(p)if st[ver]:continuest[ver] Truei h[ver]while i ! -1:j e[i]if dis[j] dis[ver] w[i]:dis[j] dis[ver] w[i]heapq.heappush(p, (dis[j], j))i ne[i]if dis[n] float(inf):return -1return dis[n]for _ in range(m):a, b, c map(int, input().split())add(a, b, c)print(dijkstra())如果存在负权边
3.bellman-ford 对于边的存储方式不高。故可以用结构体初始化。
方式初始化所有点到源点的距离为∞把源点到自己的距离设置为0遍历n次每次遍历m条边用每一条边去更新各点到源点的距离。在碰到限制了最短路径上边的长度时就只能用bellman_ford了。 for n次 for 所有边 a,b,w (松弛操作) dis[b] min(dis[b],back[a] w) //注意这里的backup非常重要为了防止串联假设限制只能用1条边 如下图如果出现这样不用之前的备份就会出现1-3最近为2而不是3所以要备份一下之前的情况用之前未更新的情况更新下一个节点。 c
#includeiostream
#include cstringusing namespace std;
const int N510,M10010;
struct edge{int a;int b;int w;
}edge[M];
int dis[N];
int backup[N];
int n,m,k;
void bellman_ford(){memset(dis,0x3f,sizeof dis);dis[1]0;for(int i0;ik;i){memcpy(backup,dis,sizeof dis);for(int j0;jm;j){auto eedge[j];dis[e.b]min(dis[e.b],backup[e.a]e.w);}}
}int main(){cinnmk;for(int i0;im;i){int x,y,z;cinxyz;edge[i]{x,y,z};
}bellman_ford();if(dis[n]0x3f3f3f3f/2) puts(impossible);//可能存在负权边else printf(%d\n, dis[n]);return 0;
}
c
#include stdio.h
#include string.h#define N 510
#define M 10010struct Edge {int a;int b;int w;
};struct Edge edge[M];
int dis[N];
int backup[N];
int n, m, k;void bellman_ford() {memset(dis, 0x3f, sizeof dis);dis[1] 0;for (int i 0; i k; i) {memcpy(backup, dis, sizeof dis);for (int j 0; j m; j) {struct Edge e edge[j];if (backup[e.a] e.w dis[e.b]) {dis[e.b] backup[e.a] e.w;}}}
}int main() {scanf(%d %d %d, n, m, k);for (int i 0; i m; i) {int x, y, z;scanf(%d %d %d, x, y, z);edge[i].a x;edge[i].b y;edge[i].w z;}bellman_ford();if (dis[n] 0x3f3f3f3f / 2) {printf(impossible\n);} else {printf(%d\n, dis[n]);}return 0;
}python:
N 510
M 10010class Edge:def __init__(self, a, b, w):self.a aself.b bself.w wedge [Edge(0, 0, 0) for _ in range(M)]
dis [float(inf)] * N
backup [0] * Ndef bellman_ford():global disdis[1] 0for _ in range(k):backup[:] dis[:]for j in range(m):e edge[j]dis[e.b] min(dis[e.b], backup[e.a] e.w)def main():global n, m, kn, m, k map(int, input().split())for i in range(m):x, y, z map(int, input().split())edge[i] Edge(x, y, z)bellman_ford()if dis[n] 0x3f3f3f3f // 2:print(impossible)else:print(dis[n])if __name__ __main__:main()Go:
package mainimport (fmt
)const N 510
const M 10010type Edge struct {a, b, w int
}var edge [M]Edge
var dis [N]int
var backup [N]int
var n, m, k intfunc bellmanFord() {for i : range dis {dis[i] 0x3f3f3f3f}dis[1] 0for i : 0; i k; i {copy(backup[:], dis[:])for j : 0; j m; j {e : edge[j]if dis[e.b] backup[e.a]e.w {dis[e.b] backup[e.a] e.w}}}
}func main() {fmt.Scan(n, m, k)for i : 0; i m; i {var x, y, z intfmt.Scan(x, y, z)edge[i] Edge{x, y, z}}bellmanFord()if dis[n] 0x3f3f3f3f/2 {fmt.Println(impossible)} else {fmt.Println(dis[n])}
}时间复杂度
4.spfa 对bellman-ford的优化不一定每条边都会更新spfa算法的想法基础。 dis[b] min(dis[b],back[a] w) 观察这个式子只有back[a]变小了我的后继dis[b]才会变小 所以我可以用一个队列在一次变化中只要有节点变小了那么就肯定会影响后继节点就放入队列之中。只要队列不空就一直类似于bfs一样进行。 时间复杂度一般最坏
//与dijkstra非常相似
#include cstring
#include iostream
#include algorithm
#include queueusing namespace std;const int N 100010;int n, m;
int h[N], w[N], e[N], ne[N], idx;
int dis[N];
bool st[N];
queueint q;
void add(int a, int b, int c)
{e[idx] b, w[idx] c, ne[idx] h[a], h[a] idx ;
}int spfa(){memset(dis,0x3f,sizeof dis);dis[1]0;q.push(1);st[1]1;while(q.size()){auto tq.front();q.pop();st[t]0;for(int ih[t];i!-1;ine[i]){int je[i];if(dis[j]dis[t]w[i]){dis[j]dis[t]w[i];if(!st[j]){q.push(j);st[j]1;}}}}
return dis[n];
}
int main()
{scanf(%d%d, n, m);memset(h, -1, sizeof h);while (m -- ){int a, b, c;scanf(%d%d%d, a, b, c);add(a, b, c);}int t spfa();if (t 0x3f3f3f3f) puts(impossible);else printf(%d\n, t);return 0;
} c
#include stdio.h
#include stdlib.h
#include string.h
#include stdbool.h #define N 100010
#define INF 0x3f3f3f3f int n, m;
int h[N], w[N], e[N], ne[N], idx;
int dis[N];
bool st[N]; typedef struct { int data;
} QueueNode; typedef struct { QueueNode q[N]; int front, rear;
} Queue; void initQueue(Queue *q) { q-front q-rear 0;
} bool isEmpty(Queue *q) { return q-front q-rear;
} void enqueue(Queue *q, int x) { q-q[q-rear].data x; q-rear (q-rear 1) % N; // 使用循环队列防止溢出
} int dequeue(Queue *q) { if (isEmpty(q)) return -1; // 队列为空返回错误标识 int x q-q[q-front].data; q-front (q-front 1) % N; return x;
} void add(int a, int b, int c) { e[idx] b, w[idx] c, ne[idx] h[a], h[a] idx;
} int spfa() { memset(dis, INF, sizeof(dis)); dis[1] 0; Queue q; initQueue(q); enqueue(q, 1); st[1] true; while (!isEmpty(q)) { int t dequeue(q); st[t] false; for (int i h[t]; i ! -1; i ne[i]) { int j e[i]; if (dis[j] dis[t] w[i]) { dis[j] dis[t] w[i]; if (!st[j]) { enqueue(q, j); st[j] true; } } } } return dis[n];
} int main() { scanf(%d%d, n, m); memset(h, -1, sizeof(h)); while (m--) { int a, b, c; scanf(%d%d%d, a, b, c); add(a, b, c); } int t spfa(); if (t INF) printf(impossible\n); else printf(%d\n, t); return 0;
} python
from collections import dequeN 100010n, m map(int, input().split())
h [-1] * N
w [0] * N
e [0] * N
ne [0] * N
dis [float(inf)] * N
st [False] * N
q deque()def add(a, b, c):global idxe[idx] bw[idx] cne[idx] h[a]h[a] idxidx 1def spfa():global disdis[1] 0q.append(1)st[1] Truewhile q:t q.popleft()st[t] Falsei h[t]while i ! -1:j e[i]if dis[j] dis[t] w[i]:dis[j] dis[t] w[i]if not st[j]:q.append(j)st[j] Truei ne[i]return dis[n]idx 0
for _ in range(m):a, b, c map(int, input().split())add(a, b, c)t spfa()if t float(inf):print(impossible)
else:print(t)5.spfa拓展判断负环 原理鸽笼原理三角不等式 使用spfa算法解决是否存在负环问题 求负环的常用方法基于SPFA一般都用方法 2该题也是用方法 2 方法 1统计每个点入队的次数如果某个点入队n次则说明存在负环 方法 2统计当前每个点的最短路中所包含的边数如果某点的最短路所包含的边数大于等于n则也说明存在环 每次做一遍spfa()一定是正确的但时间复杂度较高可能会超时。初始时将所有点插入队列中可以按如下方式理解 在原图的基础上新建一个虚拟源点从该点向其他所有点连一条权值为0的有向边。那么原图有负环等价于新图有负环。此时在新图上做spfa将虚拟源点加入队列中。然后进行spfa的第一次迭代这时会将所有点的距离更新并将所有点插入队列中。执行到这一步就等价于视频中的做法了。那么视频中的做法可以找到负环等价于这次spfa可以找到负环等价于新图有负环等价于原图有负环。得证。 1、dist[x] 记录虚拟源点到x的最短距离 2、cnt[x] 记录当前x点到虚拟源点最短路的边数初始每个点到虚拟源点的距离为0只要他能再走n步即cnt[x] n则表示该图中一定存在负环由于从虚拟源点到x至少经过n条边时则说明图中至少有n 1个点表示一定有点是重复使用 3、若dist[j] dist[t] w[i],则表示从t点走到j点能够让权值变少因此进行对该点j进行更新并且对应cnt[j] cnt[t] 1,往前走一步 注意该题是判断是否存在负环并非判断是否存在从1开始的负环因此需要将所有的点都加入队列中更新周围的点 引入一个cnt数组记录每个点经过的边数 e.g. 但是如果从1开始到不了负环地方那么就会出问题我们的解决方法是一开始把所有的点都放入队列中本质就是以每个点为起点做一遍spfa for(int i1;in;i){ st[i]1; q.push(i); } 需要再cnt基础上更改的地方 dis[j]dis[t]w[i]; cnt[j]cnt[t]1; if(cnt[j]n) return true; 还有对于cnt数组的初始化还有把spfa变成布尔函数 #include cstring
#include iostream
#include algorithm
#include queueusing namespace std;const int N 100010;int n, m;
int h[N], w[N], e[N], ne[N], idx;
int dis[N];
int cnt[N];
bool st[N];
queueint q;
void add(int a, int b, int c)
{e[idx] b, w[idx] c, ne[idx] h[a], h[a] idx ;
}bool spfa(){memset(dis,0x3f,sizeof dis);
for(int i1;in;i){st[i]1;q.push(i);
}dis[1]0;q.push(1);st[1]1;while(q.size()){auto tq.front();q.pop();st[t]0;for(int ih[t];i!-1;ine[i]){int je[i];if(dis[j]dis[t]w[i]){dis[j]dis[t]w[i];cnt[j]cnt[t]1;if(cnt[j]n) return true;if(!st[j]){q.push(j);st[j]1;}}}}
return false;
}
int main()
{scanf(%d%d, n, m);memset(h, -1, sizeof h);while (m -- ){int a, b, c;scanf(%d%d%d, a, b, c);add(a, b, c);}
if(spfa()) puts(Yes);
else puts(No);return 0;
}
多源汇最短路问题
6.Floyd算法
原题 原理基于动态规划 d[k,i,j]表示从第i个点出发到达j只经过1~k个点的最短距离 状态转移方程d[k,i,j]d[k-1,i,k]d[k-1,k,j] 发现k与k-1刚好可以消去这个维度用一个数组就可以实现 d[i,j]d[i,k]d[k,j] 算法时间复杂度
具体 假设节点序号是从1到n。 假设f[0][i][j]是一个n*n的矩阵第i行第j列代表从i到j的权值如果i到j有边那么其值就为ci,j边ij的权值。 如果没有边那么其值就为无穷大。 f[k][i][j]代表k的取值范围是从1到n在考虑了从1到k的节点作为中间经过的节点时从i到j的最短路径的长度。 比如f[1][i][j]就代表了在考虑了1节点作为中间经过的节点时从i到j的最短路径的长度。 分析可知f[1][i][j]的值无非就是两种情况而现在需要分析的路径也无非两种情况i-ji-1-j 【1】f[0][i][j]i-j这种路径的长度小于i-1-j这种路径的长度 【2】f[0][i][1]f[0][1][j]i-1-j这种路径的长度小于i-j这种路径的长度 形式化说明如下 f[k][i][j]可以从两种情况转移而来 【1】从f[k−1][i][j]转移而来表示i到j的最短路径不经过k这个节点 【2】从f[k−1][i][k]f[k−1][k][j]转移而来表示i到j的最短路径经过k这个节点 总结就是f[k][i][j]min(f[k−1][i][j],f[k−1][i][k]f[k−1][k][j]) 从总结上来看发现f[k]只可能与f[k−1]有关。 初始化与读入邻接矩阵存在自环和重边的时候 for (int i 1; i n; i )for (int j 1; j n; j )if (i j) d[i][j] 0;else d[i][j] INF;while (m -- )
{int a, b, c;scanf(%d%d%d, a, b, c);d[a][b] min(d[a][b], c);
} c
#include iostream
using namespace std;const int N 210, INF 1e9;int n, m, Q;
int d[N][N];
void floyd(){for(int k1;kn;k){for(int i1;in;i){for(int j1;jn;j){d[i][j]min(d[i][j],d[i][k]d[k][j]);}}}
}
int main()
{scanf(%d%d%d, n, m, Q);for (int i 1; i n; i )for (int j 1; j n; j )if (i j) d[i][j] 0;else d[i][j] INF;while (m -- ){int a, b, c;scanf(%d%d%d, a, b, c);d[a][b] min(d[a][b], c);}floyd();while (Q -- ){int a, b;scanf(%d%d, a, b);int t d[a][b];if (t INF / 2) puts(impossible);else printf(%d\n, t);}return 0;
}
c
#include stdio.h#define N 210
#define INF 1000000000int n, m, Q;
int d[N][N];void floyd() {for (int k 1; k n; k) {for (int i 1; i n; i) {for (int j 1; j n; j) {if (d[i][k] INF d[k][j] INF) {int new_dist d[i][k] d[k][j];if (new_dist d[i][j]) {d[i][j] new_dist;}}}}}
}int main() {scanf(%d%d%d, n, m, Q);for (int i 1; i n; i) {for (int j 1; j n; j) {if (i j) {d[i][j] 0;} else {d[i][j] INF;}}}while (m--) {int a, b, c;scanf(%d%d%d, a, b, c);if (c d[a][b]) {d[a][b] c;}}floyd();while (Q--) {int a, b;scanf(%d%d, a, b);int t d[a][b];if (t INF / 2) {puts(impossible);} else {printf(%d\n, t);}}return 0;
}java
import java.util.Scanner;public class Main {static final int N 210;static final int INF 1000000000;static int n, m, Q;static int[][] d new int[N][N];public static void 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] Math.min(d[i][j], d[i][k] d[k][j]);}}}}public static void main(String[] args) {Scanner scanner new Scanner(System.in);n scanner.nextInt();m scanner.nextInt();Q scanner.nextInt();for (int i 1; i n; i) {for (int j 1; j n; j) {if (i j) d[i][j] 0;else d[i][j] INF;}}while (m-- 0) {int a scanner.nextInt();int b scanner.nextInt();int c scanner.nextInt();d[a][b] Math.min(d[a][b], c);}floyd();while (Q-- 0) {int a scanner.nextInt();int b scanner.nextInt();int t d[a][b];if (t INF / 2) {System.out.println(impossible);} else {System.out.println(t);}}scanner.close();}
}python:
import sysN 210
INF 10**9def floyd():global n, dfor k in range(1, n1):for i in range(1, n1):for j in range(1, n1):d[i][j] min(d[i][j], d[i][k] d[k][j])if __name__ __main__:n, m, Q map(int, input().split())d [[INF for _ in range(N)] for _ in range(N)]for i in range(1, n1):d[i][i] 0for _ in range(m):a, b, c map(int, input().split())d[a][b] min(d[a][b], c)floyd()for _ in range(Q):a, b map(int, input().split())t d[a][b]if t INF // 2:print(impossible)else:print(t)Go语言
package mainimport fmtconst N 210
const INF 1000000000var n, m, Q int
var d [N][N]intfunc floyd() {for k : 1; k n; k {for i : 1; i n; i {for j : 1; j n; j {if d[i][k] INF d[k][j] INF {newDist : d[i][k] d[k][j]if newDist d[i][j] {d[i][j] newDist}}}}}
}func main() {fmt.Scanf(%d%d%d, n, m, Q)for i : 1; i n; i {for j : 1; j n; j {if i j {d[i][j] 0} else {d[i][j] INF}}}for m 0 {var a, b, c intfmt.Scanf(%d%d%d, a, b, c)if c d[a][b] {d[a][b] c}m--}floyd()for Q 0 {var a, b intfmt.Scanf(%d%d, a, b)t : d[a][b]if t INF/2 {fmt.Println(impossible)} else {fmt.Println(t)}Q--}
}
