最短路径算法

关注：算法思路，时间复杂度，适用情况（单源/多源，负边权/负边权回路）

复习弗雷德算法--基于动态规划--多源--负边权--时间复杂度O(v^3)

 int的最大值是0x7fffffff

#include <iostream>  
using namespace std;
#define inf 100000
int n, m;
int a[105][105];
int dp[105][105];
int main() {cin >> n >> m;for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {a[i][j] = inf;if (i == j) {a[i][j] = 0;}}}int x, y, w;for (int i = 1; i <= m; i++) {cin >> x >> y >> w;a[x][y] = w;}//初始化dpfor (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {dp[i][j] = a[i][j];}}for (int k = 1; k <= n; k++) {//枚举中转点for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {dp[i][j] = min(dp[i][j], dp[k - 1][i] + dp[k][j]);//不能交换循环位置，无法解释了}}}for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {cout << dp[i][j] << " ";}cout << endl;}return 0;
}

复习迪斯拉算法--基于贪心--单源--不能处理负边权--时间复杂度O(v^3)

#include<iostream>
using namespace std;
#define INF 65535
int g[105][105];
int dist[105], path[105];
int flag[105];//==1  i的最短路径已经确定
int n, m;
void Dijkstra(int s) {//起点到起点flag[s] = 1;dist[s] = 0;path[s] = s;int minn = INF;int t;for (int i = 1; i < n; i++) {//循环n-1次minn = INF;for (int j = 0; j < n; j++) {if (flag[j] == 0 && dist[j] < minn) {minn = dist[j];t = j;//t点是dist最小的点}}flag[t] = 1;//确定最小路径for (int j = 0; j < n; j++) {if (flag[j] == 0 && dist[j] > (dist[t] + g[t][j])) {dist[j] = dist[t] + g[t][j];path[j] = t;}}}}
int main() {int s;//起点cin >> n >> m;for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (i == j)g[i][j] = 0;else g[i][j] = INF;}}int x, y, w;for (int i = 1; i <= m; i++) {cin >> x >> y >> w;g[x][y] = g[y][x] = w;}cin >> s;dist[s] = 0;for (int i = 0; i < n; i++) {dist[i] = g[s][i];if (g[s][i] == INF) {path[i] = -1;}else {path[i] = s;}}Dijkstra(s);for (int i = 0; i < n; i++) {cout << "s到" << i << "的最短路径长度是" << dist[i] << ":";//倒叙输出路径cout << i << " ";int j = i;while (path[j] != j) {cout << path[j] << " ";j = path[j];}cout << endl;}return 0;
}
//9 16
//0 1 1
//0 2 5
//1 2 3
//1 3 7
//1 4 5
//2 4 1
//2 5 7
//3 4 2
//3 6 3
//4 5 3
//4 6 6
//4 7 9
//5 7 5
//6 7 2
//6 8 7
//7 8 4
//0

 优化：无序找最小(通过小顶堆)--邻接表存图--链式前向星--priority_quque从n到logn

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
typedef pair<int, int> PII;
int n, m, cut;
int flag[105];
int dis[105];
int s;//起点
struct Edge {int to, next, w;
}e[10005];
int head[105];
priority_queue<PII, vector<PII>, greater<PII>>q;
void add(int x,int y,int w) {cut++;//从1开始e[cut].to = y;e[cut].w = w;e[cut].next = head[x];head[x] = cut;cut++;
}void dijkstra() {memset(dis, 0x3f3f3f3f, sizeof(dis));dis[s] = 0;q.push({ 0,s });while (q.size()) {PII t = q.top();q.pop();int u = t.second, d = t.first;if (flag[u] == 1)continue;flag[u] = 1;for (int i = head[u]; i != -1; i = e[i].next) {//i即u的出边int v = e[i].to;//u的邻接点if (flag[v] == 0 && dis[v] > dis[u] + e[i].w) {dis[v] = dis[u] + e[i].w;q.push({ dis[v],v });}}}
}
int main() {scanf("%d %d %d", &n, &m, &s);int x, y, w;memset(head, -1, sizeof(head));for (int i = 1; i <= m; i++) {scanf("%d %d %d", &x, &y, &w);add(x, y, w);}dijkstra();for (int i = 1; i <= n; i++) {printf("%d ", dis[i]);}return 0;
}
//4 5 1
//1 2 1
//1 4 1
//2 3 2
//4 3 2
//1 3 6

弗雷德和迪斯拉算法共性

 福特算法Bellman-Ford算法--暴力遍历无脑松弛--单源--时间复杂度O(ve)--能处理负边权--不能处理负权回路，但是能判断是否有负权回路（让他循环到n次）

 

#include<iostream>
#include<vector>
using namespace std;
int n, m;
int dis[105];
int s;//起点
struct Edge {int a, b, w;
}e[10005];
void ford() {int x, y, w;bool flag = 0;for (int i = 1; i <= n - 1; i++) {flag = 0;for (int j = 0; j < m; j++) {x = e[j].a;y = e[j].b;w = e[j].w;if (dis[x] + w < dis[y]) {dis[y] = dis[x] + w;flag = 1;}}if (flag == 0)break;//没有松弛操作，说明全部已经松弛了}
}int main() {scanf("%d %d", &n, &m);for (int i = 0; i < m; i++) {scanf("%d %d %d", &e[i].a, &e[i].b, &e[i].w);}scanf("%d", &s);memset(dis, 0x3f3f3f3f, sizeof(dis));dis[s] = 0;ford();for (int i = 1; i <= n; i++) {printf("%d ", dis[i]);}return 0;
}
//5 5
//2 3 2
//1 2 - 3
//1 5 5
//4 5 2
//3 4 3
//1

下面改一点点能判断有负权回路（负环）

#include<iostream>
#include<vector>
using namespace std;
int n, m;
int dis[105];
int s;//起点
struct Edge {int a, b, w;
}e[10005];
void ford() {int x, y, w;bool flag = 0;for (int i = 1; i <= n; i++) {//执行第n次flag = 0;for (int j = 0; j < m; j++) {x = e[j].a;y = e[j].b;w = e[j].w;if (dis[x] + w < dis[y]) {//第n次不执行松弛操作dis[y] = dis[x] + w;flag = 1;}}//if (flag == 0)break;//没有松弛操作，说明全部已经松弛了}if (flag == 1)printf("有负权回路");else printf("没有负权回路");
}int main() {scanf("%d %d", &n, &m);for (int i = 0; i < m; i++) {scanf("%d %d %d", &e[i].a, &e[i].b, &e[i].w);}scanf("%d", &s);memset(dis, 0x3f3f3f3f, sizeof(dis));dis[s] = 0;ford();for (int i = 1; i <= n; i++) {printf("%d ", dis[i]);}return 0;
}
//5 5
//2 3 2
//1 2 - 3
//1 5 5
//4 5 2
//3 4 3
//1

缺点：枚举顺序导致时间长一点,可以优化，优化后就是SPFA算法。

SPFA算法：能判断负环--时间复杂度难以计算

 

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
typedef pair<int, int> PII;
int n, m, cut;
int flag[105];
int dis[105];
int s;//起点
struct Edge {int to, next, w;
}e[10005];
int head[105];
priority_queue<PII, vector<PII>, greater<PII>>q;
void add(int x,int y,int w) {cut++;//从1开始e[cut].to = y;e[cut].w = w;e[cut].next = head[x];head[x] = cut;cut++;
}
void SPFA() {queue<int>q;memset(dis, 0x3f3f3f3f, sizeof(dis));dis[s] = 0;flag[s] = 1;//标记s有没有被入队q.push(s);while (!q.empty()) {int u = q.front();q.pop();flag[u] = 0;for (int i = head[u]; i != -1; i = e[i].next) {int v = e[i].to;//v是u的邻接点if (flag[v] == 0 && dis[v] > dis[u] + e[i].w) {dis[v] = dis[u] + e[i].w;q.push(v);flag[v] = 1;}}}
}
int main() {scanf("%d %d %d", &n, &m, &s);int x, y, w;memset(head, -1, sizeof(head));for (int i = 1; i <= m; i++) {scanf("%d %d %d", &x, &y, &w);add(x, y, w);}SPFA();for (int i = 1; i <= n; i++) {printf("%d ", dis[i]);}return 0;
}
//5 5 1
//2 3 2
//1 2 - 3
//1 5 5
//4 5 2
//3 4 3

判负环加上use（以下代码只比上一个代码多use但是已经注释）

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
typedef pair<int, int> PII;
int n, m, cut;
int flag[105];
int dis[105];
//int use[105];//用于判断负环
int s;//起点
struct Edge {int to, next, w;
}e[10005];
int head[105];
priority_queue<PII, vector<PII>, greater<PII>>q;
void add(int x,int y,int w) {cut++;//从1开始e[cut].to = y;e[cut].w = w;e[cut].next = head[x];head[x] = cut;cut++;
}
void SPFA() {queue<int>q;memset(dis, 0x3f3f3f3f, sizeof(dis));dis[s] = 0;flag[s] = 1;//标记s有没有被入队//use[s]++;q.push(s);while (!q.empty()) {int u = q.front();q.pop();flag[u] = 0;for (int i = head[u]; i != -1; i = e[i].next) {int v = e[i].to;//v是u的邻接点if (flag[v] == 0 && dis[v] > dis[u] + e[i].w) {dis[v] = dis[u] + e[i].w;q.push(v);//use[v]++;flag[v] = 1;//if(use[v]>=n)}}}
}
int main() {scanf("%d %d %d", &n, &m, &s);int x, y, w;memset(head, -1, sizeof(head));for (int i = 1; i <= m; i++) {scanf("%d %d %d", &x, &y, &w);add(x, y, w);}SPFA();for (int i = 1; i <= n; i++) {printf("%d ", dis[i]);}return 0;
}
//5 5 1
//2 3 2
//1 2 - 3
//1 5 5
//4 5 2
//3 4 3

 时间复杂度吃瓜