Floyd算法特点
1、适合求多源最短路径
2、可以求最小环
3、可以有负边权,不能有负环
4、可以求有向图的传递闭包
5、时间复杂度O(n^3)
单源最短路径算法的选择?
Dijkstra + 堆优化?无法处理负边权的问题
SPFA + 堆优化?期望复杂度很优秀,但是复杂度不稳定
基于本书面向的是计算机考研机试,几乎不可能出现故意构造大量数据使得SPFA超时的情况发生,就如同不可能在机试中故意构造数据使得sort函数的复杂度退化到O(n^2)一样。
当然,也为了防止本书爆红之后被出题老师故意针对,后面我们也附上Dijkstra的通用算法模板以备不时之需。
最短路
题目描述:
在每年的校赛里,所有进入决赛的同学都会获得一件很漂亮的t-shirt。但是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候,却是非常累的!所以现在他们想要寻找最短的从商店到赛场的路线,你可以帮助他们吗?
输入描述:
输入包括多组数据。每组数据第一行是两个整数N、M(N<=100,M<=10000),N表示成都的大街上有几个路口,标号为1的路口是商店所在地,标号为N的路口是赛场所在地,M则表示在成都有几条路。N=M=0表示输入结束。接下来M行,每行包括3个整数A,B,C(1<=A,B<=N,1<=C<=1000),表示在路口A与路口B之间有一条路,我们的工作人员需要C分钟的时间走过这条路。
输入保证至少存在1条商店到赛场的路线。
输出描述:
对于每组输入,输出一行,表示工作人员从商店走到赛场的最短时间
输入样例#:
2 1
1 2 3
3 3
1 2 5
2 3 5
3 1 2
0 0
输出样例#:
3
2
题目来源:
DreamJudge 1565
题目解析:最短路径的模板题,直接使用最短路径模板算法即可。
参考代码(通用模板)
/*
spfa + vector
SPFA可以有负边权、可以用一点个入队是否超过N次判断是否存在负环
*/
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
const int maxn = 105;
int n, m;
struct Edge{
int u, v, w;
Edge(int u, int v, int w):u(u),v(v),w(w) {}
};
vector<Edge> edges;
vector<int> G[maxn];
int dist[maxn]; // 存放起点到i点的最短距离
int vis[maxn]; // 标记是否访问过
int p[maxn]; // 存放路径
void spfa(int s) {
queue<int> q; // 如果这个spfa超时的时候可以把队列改为和dijkstra一样的优先队列
for (int i = 0; i <= n; i++) dist[i] = INF;
dist[s] = 0;
memset(vis, 0, sizeof(vis));
q.push(s);
while (!q.empty()) {
int u = q.front(); q.pop();
vis[u] = 0;
for (int i = 0; i < G[u].size(); i++) {
Edge& e = edges[G[u][i]];
if (dist[e.v] > dist[u] + e.w) { // 松弛过程
dist[e.v] = dist[u] + e.w;
p[e.v] = u; // 松弛过程 记录路径
if (!vis[e.v]) {
vis[e.v] = 1;
q.push(e.v);
}
}
}
}
}
void addedge(int u, int v, int w) {
edges.push_back(Edge(u, v, w));
int sz = edges.size();
G[u].push_back(sz - 1);
}
void init() {
for(int i = 0; i <= n; i++) G[i].clear();
edges.clear();
}
int main() {
while (scanf("%d%d", &n, &m) != EOF) {
if (n + m == 0) break;
init();
for (int i = 0; i < m; i++) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
addedge(a, b, c);
addedge(b, a, c);
}
spfa(1);
printf("%d\n",dist[n]);
}
return 0;
}
参考代码(floyd模板)
/*
flody算法可以求多源最短路径
*/
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
const int maxn = 105;
int mpt[maxn][maxn];
int n, m;
void floyd() {
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
mpt[i][j] = min(mpt[i][k] + mpt[k][j], mpt[i][j]);
}
}
}
}
int main() {
while (scanf("%d%d", &n, &m) != EOF) {
if (n + m == 0) break;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i == j) mpt[i][j] = 0;
else mpt[i][j] = INF;
}
}
for (int i = 1; i <= m; i++) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
if (c < mpt[a][b]) { //注意重边
mpt[a][b] = c;
mpt[b][a] = c;
}
}
floyd();
printf("%d\n",mpt[1][n]);
}
return 0;
}
参考代码(dijkstra模板)
// dijkstra + 堆优化
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
const int maxn = 105;
int n, m;
struct Edge{
int u, v, w;
Edge(int u, int v, int w):u(u),v(v),w(w) {}
};
struct node {
int d, u;
node(int d, int u):d(d),u(u) {}
friend bool operator < (node a, node b) {
return a.d > b.d;
}
};
vector<Edge> edges;
vector<int> G[maxn];
int dist[maxn]; // 存放起点到i点的最短距离
int vis[maxn]; // 标记是否访问过
int p[maxn]; // 存放路径
void dijkstra(int s) {
priority_queue<node> q;
for (int i = 0; i <= n; i++) dist[i] = INF;
dist[s] = 0;
memset(vis, 0, sizeof(vis));
q.push(node(0, s));
int cnt = 0; //统计松弛次数
while (!q.empty()) {
node now = q.top(); q.pop();
int u = now.u;
if (vis[u]) continue;
vis[u] = 1;
cnt++;
if(cnt >= n) break; // 小优化
for (int i = 0; i < G[u].size(); i++) { // // Sum -> O(E)
Edge& e = edges[G[u][i]];
if (dist[e.v] > dist[u] + e.w) { // O(lgV)
dist[e.v] = dist[u] + e.w;
p[e.v] = G[u][i];
q.push(node(dist[e.v], e.v));
}
}
}
}
void addedge(int u, int v, int w) {
edges.push_back(Edge(u, v, w));
int sz = edges.size();
G[u].push_back(sz - 1);
}
void init() {
for(int i = 0; i <= n; i++) G[i].clear();
edges.clear();
}
int main() {
while (scanf("%d%d", &n, &m) != EOF) {
if (n + m == 0) break;
init();
for (int i = 0; i < m; i++) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
addedge(a, b, c);
addedge(b, a, c);
}
dijkstra(1);
printf("%d\n",dist[n]);
}
return 0;
}
由于部分同学只能使用C语言进行机试,下面给出C语言实现的最短路算法模板。
SPFA算法模板(C语言实现)
#include<stdio.h>
#include<string.h>
#define INF 0x7ffffff
struct node {
int to, next, val;
}edge[100005];//边的数量100005
int head[1005];//点的数量1005
int dist[1005];
int vis[1005];
int Q[100005];//定义一个数组模拟的队列
void SPFA(int s, int n) {//SPFA算法模板
int l = 0;//定义队首
int r = 0;//定义队尾
memset(vis,0,sizeof(vis));
for(int i = 1; i <= n; i++)
dist[i] = INF;
dist[s] = 0;
vis[s] = 1;
Q[r++] = s;//将起点入队
while (l < r) {//当队列不为空
int now = Q[l];//取队首元素
l++; //出队
vis[now] = 0;
for(int i = head[now];i != -1;i = edge[i].next) {
int to = edge[i].to;
if(dist[to] > dist[now] + edge[i].val) {
dist[to] = dist[now] + edge[i].val;
if(vis[to] == 0) {
vis[to] = 1;
Q[r++] = to; //将点to入队
}
}
}
}
}
int k;
void init() {//初始化
k = 0;
memset(head, -1, sizeof(head));
}
void add(int x, int y, int val) {//加边操作
edge[k].to = y;
edge[k].val = val;
edge[k].next = head[x];
head[x] = k++;
}
int main() {
int n, m;
while(scanf("%d%d", &n, &m) != EOF){
if(n == 0 && m == 0)break;
init();
int a, b, c;
for(int i = 1; i <= m; i++) {
scanf("%d%d%d", &a, &b, &c);
add(a, b, c);//加入有向边a->b权值为c
add(b, a, c);
}
SPFA(1, n);//传入起点和点的数量
printf("%d\n", dist[n]);
}
return 0;
}
练习题目
DreamJudge 1344 最短路径问题
DreamJudge 1286 最短路径
DreamJudge 1224 I Wanna Go Home
登录后开始许愿
暂无评论,来抢沙发