《算法笔记》10.4小节——图算法专题-＞最短路径
·
10.4.1 Dijkstra算法
解决单源最短路径问题
D算法可以用堆进行排序优化；D算法只能应对所有边权都是非负数的情况，如果边权出现负数，那么D算法很容易出错，最好使用SPFA算法
PAT A1003 Emergency
题目见书上P378
#define _CRT_SECURE_NO_WARNINGS 1
#include <cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxv = 510;
const int INF = 1000000000;//无穷大
//n=城市数，m=道路数，st ed是起点和终点，G[][]是邻接矩阵，表示无向图，weight表示各个点权
int n, m, st, ed, G[maxv][maxv], weight[maxv];
//d[i]表示到点i的最短距离，w[i]表示到点i的最大点权之和，num[i]表示到点i的最短路径的条数
int d[maxv], w[maxv], num[maxv];
//=1表示已经访问过，计算出来最短路径了，=1就表示还没有访问
int vis[maxv] = {0};
void Dijkstra(int s)
{
//初始化
fill(d, d + maxv, INF);//到所有点的距离都是无穷大
memset(num, 0, sizeof(num));//对端路径条数为1
memset(w, 0, sizeof(w));//点权之和为0
//下面初始化起点
d[s] = 0;
w[s] = weight[s];
num[s] = 1;
//初始化完成
for (int i = 0; i < n; i++)
{
//首先找到最小的还未被访问的顶点标号
int u = -1, MIN = INF;
for (int j = 0; j < n; j++)
{
if (vis[j] == 0 && d[j] < MIN)
{
u = j;
MIN = d[j];
}
}
if (u == -1) return;
vis[u] = 1;//记u被访问过
for (int v = 0; v < n; v++)
{
if (vis[v] == 0 && G[u][v] != INF)//枚举从U出发所有能到达的顶点v
{
if (d[u] + G[u][v] < d[v])//如果小于
{
d[v] = d[u] + G[u][v];//优化d[v]
w[v] = w[u] + weight[v];//点权之和要相加
num[v] = num[u];//到v的最短路径条数等于到u的路径条数
}
else if (d[u] + G[u][v] == d[v])//如果等于
{
if (w[u] + weight[v] > w[v])//那么点权较大的时候才优化
w[v] = w[u] + weight[v];
num[v] += num[u];//到v的路径条数要加上到u的路径条数
}
}
}
}
}
int main()
{
scanf("%d%d%d%d",&n,&m,&st,&ed);//输入城市数，道路数，起点和终点
for (int i = 0; i < n; i++)
{
scanf("%d",&weight[i]);//输入各个城市的救援队数量
}
int u, v;
fill(G[0], G[0] + maxv * maxv, INF);//初始化邻接矩阵所有元素都为无穷大
for (int i = 0; i < m; i++)
{
scanf("%d%d",&u,&v);//输入两个城市的编号
//下面两行给无向图的边赋值
scanf("%d",&G[u][v]);
G[v][u] = G[u][v];
}
//至此，初始化完成
Dijkstra(st);
printf("%d %d\n",num[ed],w[ed]);//输出到终点的最短路径条数，输出最大的点权之和
return 0;
}
D算法+DFS
先记录所有最短路径，然后从所有路径中选择则以条第二标尺最优的路径
分两步走：
①D算法记录所有的最短路径
②遍历所有的最短路径
PAT A1030 Travel Plan
题目见书上P385
D算法：
#define _CRT_SECURE_NO_WARNINGS 1
#include <cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxv = 510;
const int INF = 1000000000;//无穷大
//n=城市数，m=道路数，st ed是起点和终点，G[][]是邻接矩阵，表示无向图，weight表示各个点权
int n, m, st, ed, G[maxv][maxv], cost[maxv][maxv];
//d[i]表示到点i的最短距离，c[i]表示到点i的最大点权之和，pre[i]表示到点i的前面一个点
int d[maxv], c[maxv],pre[maxv];
//=1表示已经访问过，计算出来最短路径了，=1就表示还没有访问
int vis[maxv] = {0};
void Dijkstra(int s)
{
//初始化
fill(d, d + maxv, INF);//到所有点的距离都是无穷大
fill(c, c + maxv, INF);
//下面初始化起点
d[s] = 0;
c[s] = 0;
//初始化完成
for (int i = 0; i < n; i++)
{
//首先找到最小的还未被访问的顶点标号
int u = -1, MIN = INF;
for (int j = 0; j < n; j++)
{
if (vis[j] == 0 && d[j] < MIN)
{
u = j;
MIN = d[j];
}
}
if (u == -1) return;
vis[u] = 1;//记u被访问过
for (int v = 0; v < n; v++)
{
if (vis[v] == 0 && G[u][v] != INF)//枚举从U出发所有能到达的顶点v
{
if (d[u] + G[u][v] < d[v])//如果小于
{
d[v] = d[u] + G[u][v];//优化d[v]
c[v] = c[u] + cost[u][v];//点权之和要相加
pre[v] =u;//到v的最短路径条数等于到u的路径条数
}
else if (d[u] + G[u][v] == d[v])//如果等于
{
if (c[u] + cost[u][v] < c[v])//那么点权较大的时候才优化
{
c[v] = c[u] + cost[u][v];//点权之和要相加
pre[v] = u;
}
}
}
}
}
}
void DFS(int v)
{
if (v == st)
{
printf("%d ",v);
return;
}
DFS(pre[v]);
printf("%d ",v);
}
int main()
{
scanf("%d%d%d%d",&n,&m,&st,&ed);//输入城市数，道路数，起点和终点
int u, v;
fill(G[0], G[0] + maxv * maxv, INF);//初始化邻接矩阵所有元素都为无穷大
for (int i = 0; i < m; i++)
{
scanf("%d%d%",&u,&v);//输入两个城市的编号
scanf("%d%d", &G[u][v], &cost[u][v]);
//下面两行给无向图的边赋值以及花费
G[v][u] = G[u][v];
cost[v][u] = cost[u][v];
}
//至此，初始化完成
Dijkstra(st);
DFS(ed);
printf("%d %d\n",d[ed],c[ed]);//输出到终点的最短路径条数，输出最大的点权之和
return 0;
}
D算法+DFS：
这个和纯D算法的区别是D算法精确的算出来唯一的pre[i].而在D+DFS中，D算法只需要算出来最短路径树即可，使用DFS枚举这棵树，找到最优的cost
#define _CRT_SECURE_NO_WARNINGS 1
#include <cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int maxv = 510;
const int INF = 1000000000;//无穷大
//n=城市数，m=道路数，st ed是起点和终点，G[][]是邻接矩阵，表示无向图，weight表示各个点权
int n, m, st, ed, G[maxv][maxv], cost[maxv][maxv];
//d[i]表示到点i的最短距离，c[i]表示到点i的最大点权之和，pre[i]表示到点i的前面一个点
int d[maxv], minCost=INF;
//=1表示已经访问过，计算出来最短路径了，=1就表示还没有访问
int vis[maxv] = {0};
vector<int> pre[maxv];
vector<int> tempPath, path;
void Dijkstra(int s)
{
//初始化
fill(d, d + maxv, INF);//到所有点的距离都是无穷大
//下面初始化起点
d[s] = 0;
//初始化完成
for (int i = 0; i < n; i++)
{
//首先找到最小的还未被访问的顶点标号
int u = -1, MIN = INF;
for (int j = 0; j < n; j++)
{
if (vis[j] == 0 && d[j] < MIN)
{
u = j;
MIN = d[j];
}
}
if (u == -1) return;
vis[u] = 1;//记u被访问过
for (int v = 0; v < n; v++)
{
if (vis[v] == 0 && G[u][v] != INF)//枚举从U出发所有能到达的顶点v
{
if (d[u] + G[u][v] < d[v])//如果小于
{
d[v] = d[u] + G[u][v];//优化d[v]
pre[v].clear();
pre[v].push_back(u);
}
else if (d[u] + G[u][v] == d[v])//如果等于
{
pre[v].push_back(u);
}
}
}
}
}
void DFS(int v)
{
if (v == st)
{
tempPath.push_back(v);
int tempCost = 0;
for (int i = tempPath.size() - 1; i > 0; i--)
{
int id = tempPath[i];
int idnext = tempPath[i - 1];
tempCost += cost[id][idnext];
}
if (tempCost < minCost)
{
minCost = tempCost;
path = tempPath;
}
tempPath.pop_back();
return;
}
tempPath.push_back(v);
for (int i = 0; i < pre[v].size(); i++)
{
DFS(pre[v][i]);
}
tempPath.pop_back();
}
int main()
{
scanf("%d%d%d%d",&n,&m,&st,&ed);//输入城市数，道路数，起点和终点
int u, v;
fill(G[0], G[0] + maxv * maxv, INF);//初始化邻接矩阵所有元素都为无穷大
for (int i = 0; i < m; i++)
{
scanf("%d%d%",&u,&v);//输入两个城市的编号
scanf("%d%d", &G[u][v], &cost[u][v]);
//下面两行给无向图的边赋值以及花费
G[v][u] = G[u][v];
cost[v][u] = cost[u][v];
}
//至此，初始化完成
Dijkstra(st);
DFS(ed);
for (int i = path.size() - 1; i >= 0; i--)
{
printf("%d ",path[i]);
}
printf("%d %d\n",d[ed],minCost);//输出到终点的最短路径条数，输出最大的点权之和
return 0;
}
10.4.2 BF算法和SPFA算法
BF算法可以解决单源最短路径问题，也能处理有负权边的情况。
10.4.3 Floyd算法
解决全员全源路径问题：
求任意两点u和v之间的最短路径长度，时间复杂度是n3,所以顶点n一般限制在200以内，使用邻接矩阵来实现Floyd算法比较合适。
需要注意最外层的k循环不可以放在内层
习题
问题 A: 算法7-15：迪杰斯特拉最短路径算法
问题描述：在本题中，读入一个有向图的带权邻接矩阵（即数组表示），建立有向图并按照以上描述中的算法求出源点至每一个其它顶点的最短路径长度。
- 输入
输入的第一行包含2个正整数n和s，表示图中共有n个顶点，且源点为s。其中n不超过50，s小于n。
以后的n行中每行有n个用空格隔开的整数。对于第i行的第j个整数，如果大于0，则表示第i个顶点有指向第j个顶点的有向边，且权值为对应的整数值；如果这个整数为0，则表示没有i指向j的有向边。当i和j相等的时候，保证对应的整数为0。
- 输出
只有一行，共有n-1个整数，表示源点至其它每一个顶点的最短路径长度。如果不存在从源点至相应顶点的路径，输出-1。
请注意行尾输出换行。
- 样例输入
4 1
0 3 0 1
0 0 4 0
2 0 0 0
0 0 1 0
- 样例输出
6 4 7
最基础的D算法，注意序号是从0-n-1算的
#define _CRT_SECURE_NO_WARNINGS 1
#include <cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxv = 60;
const int INF = 1000000000;//无穷大
int n,st, G[maxv][maxv];
//d[i]表示到点i的最短距离
int d[maxv];
int vis[maxv] = {0};
void Dijkstra(int s)
{
//初始化
fill(d, d + maxv, INF);//到所有点的距离都是无穷大
d[s] = 0;
for (int i = 0; i < n; i++)
{
//首先找到最小的还未被访问的顶点标号
int u = -1, MIN = INF;
for (int j = 0; j < n; j++)
{
if (vis[j] == 0 && d[j] < MIN)
{
u = j;
MIN = d[j];
}
}
if (u == -1) return;
vis[u] = 1;//记u被访问过
for (int v = 0; v < n; v++)
{
if (vis[v] == 0 && G[u][v] != INF&& d[u] + G[u][v] < d[v])//枚举从U出发所有能到达的顶点v
{
d[v] = d[u] + G[u][v];//优化d[v]
}
}
}
}
int main()
{
scanf("%d %d",&n,&st);//输入城市数，道路数，起点和终点
int temp;
fill(G[0], G[0] + maxv * maxv, INF);//初始化邻接矩阵所有元素都为无穷大
for (int i = 0; i <n; i++)
{
for (int j = 0; j < n; j++)
{
scanf("%d", &temp);
if (temp != 0)
G[i][j] = temp;
}
}
//至此，初始化完成
Dijkstra(st);
for (int i = 0; i < n; i++)
{
if (i != st)
{
if (d[i] != INF)
printf("%d ", d[i]);
else
printf("-1 ");
}
}
return 0;
}
问题 B: 算法7-16：弗洛伊德最短路径算法
问题描述：在本题中，读入一个有向图的带权邻接矩阵（即数组表示），建立有向图并按照以上描述中的算法求出每一对顶点间的最短路径长度。
- 输入
输入的第一行包含1个正整数n，表示图中共有n个顶点。其中n不超过50。
以后的n行中每行有n个用空格隔开的整数。对于第i行的第j个整数，如果大于0，则表示第i个顶点有指向第j个顶点的有向边，且权值为对应的整数值；如果这个整数为0，则表示没有i指向j的有向边。当i和j相等的时候，保证对应的整数为0。
- 输出
共有n行，每行有n个整数，表示源点至每一个顶点的最短路径长度。如果不存在从源点至相应顶点的路径，输出-1。对于某个顶点到其本身的最短路径长度，输出0。
请在每个整数后输出一个空格，并请注意行尾输出换行。
- 样例输入
4
0 3 0 1
0 0 4 0
2 0 0 0
0 0 1 0
- 样例输出
0 3 2 1
6 0 4 7
2 5 0 3
3 6 1 0
#define _CRT_SECURE_NO_WARNINGS 1
#include <cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxv = 60;
const int INF = 1000000000;//无穷大
int n,st, G[maxv][maxv];
//d[i]表示到点i的最短距离
int dis[maxv][maxv];
int vis[maxv] = {0};
void Floyd()
{
for (int k = 0; k < n; k++)
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (dis[i][k] != INF && dis[k][j] != INF && dis[i][k] + dis[k][j] < dis[i][j])
dis[i][j] = dis[i][k] + dis[k][j];
}
}
}
}
int main()
{
scanf("%d",&n);//输入城市数，道路数，起点和终点
int temp;
fill(dis[0], dis[0] + maxv * maxv, INF);//初始化邻接矩阵所有元素都为无穷大
for (int i = 0; i <n; i++)
{
for (int j = 0; j < n; j++)
{
scanf("%d", &temp);
if (temp != 0)
dis[i][j] = temp;
}
}
//至此，初始化完成
Floyd();
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (i == j)
printf("0 ");
else if(dis[i][j] != INF)
printf("%d ", dis[i][j]);
else
printf("-1 ");
}
printf("\n");
}
return 0;
}
⭐⭐⭐问题 C: 最短路径
问题描述：N个城市，标号从0到N-1，M条道路，第K条道路（K从0开始）的长度为2^K，求编号为0的城市到其他城市的最短距离。
- 输入
第一行两个正整数N（2<=N<=100）M(M<=500),表示有N个城市，M条道路，
接下来M行两个整数，表示相连的两个城市的编号。
- 输出
N-1行，表示0号城市到其他城市的最短路，如果无法到达，输出-1，数值太大的以MOD 100000 的结果输出。
- 样例输入
4 3
0 1
1 2
2 0
- 样例输出
1
3
-1
这题乍一看比较简单，实际需要结合并查集还有快速幂来判断
#define _CRT_SECURE_NO_WARNINGS 1
#include <cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#include<string>
#include<vector>
#include<iostream>
using namespace std;
int g[101][101];
bool visit[101];
int father[101], d[101];
int n;
int INF = 0x3fffffff;
int f(int k)
{
int s = 1;
for (int i = 1; i <= k; i++)
{
s = (s * 2) % 100000;
}
return s;
}
void dij(int s)
{
int i, j;
fill(visit, visit + 101, false);
fill(d, d + 101, INF);
for (i = 0; i < n; i++)
{
d[i] = g[s][i];
}
d[s] = 0;
visit[s] = true;
for (i = 1; i < n; i++)
{
int Min = INF;
int u = -1;
for (j = 0; j < n; j++)
{
if (visit[j] == false && d[j] < Min)
{
Min = d[j];
u = j;
}
}
if (u == -1)return;
visit[u] = true;
for (j = 0; j < n; j++)
{
if (visit[j] == false && g[u][j] + d[u] < d[j])
d[j] = d[u] + g[u][j];
}
}
}
int findFather(int x)
{
while (x != father[x])
x = father[x];
return x;
}
int main()
{
int m, i, a, b;
while (scanf("%d %d", &n, &m) != EOF)
{
for (i = 0; i < n; i++)father[i] = i;
fill(g[0], g[0] + 101 * 101, INF);
for (i = 0; i < m; i++)
{
scanf("%d %d", &a, &b);
int fatherA = findFather(a);
int fatherB = findFather(b);
if (fatherA != fatherB)
{
father[fatherA] = fatherB;
g[a][b] = g[b][a] = f(i);//如果不是
}
else continue;
}
dij(0);
for (i = 1; i < n; i++)
{
if (d[i] == INF)printf("-1\n");
else printf("%d\n", d[i] % 100000);
}
}
return 0;
}
问题 D: 最短路径
问题描述：有n个城市m条道路（n<1000, m<10000)，每条道路有个长度，请找到从起点s到终点t的最短距离和经过的城市名。
- 输入
输入包含多组测试数据。
每组第一行输入四个数，分别为n，m，s，t。
接下来m行，每行三个数，分别为两个城市名和距离。
- 输出
每组输出占两行。
第一行输出起点到终点的最短距离。
第二行输出最短路径上经过的城市名，如果有多条最短路径，输出字典序最小的那条。若不存在从起点到终点的路径，则输出“can't arrive”。
- 样例输入
3 3 1 3
1 3 3
1 2 1
2 3 1
- 样例输出
2
1 2 3
注意是多点测试！
使用邻接表做：
#define _CRT_SECURE_NO_WARNINGS 1
#include <cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int maxv = 1010;
const int INF = 1000000000;//无穷大
struct Node {
int v, dis;//边的终点，边权
Node(int x, int y) :v(x), dis(y) {};//初始化函数
};
vector<Node> Adj[maxv];
int pre[maxv];
//vector<int>pre[maxv], temppath,path;//前置变长数组，临时路径，路径
int n, m, s, t;//记录前驱节点
//d[i]表示到点i的最短距离
int d[maxv];
int vis[maxv] = { 0 };
void Dijkstra(int s)
{
//初始化
fill(d, d + maxv, INF);//到所有点的距离都是无穷大
fill(vis, vis + maxv, 0);//注意一定要初始化！！！
for (int i = 1; i <= n; i++)
pre[i] = i;
d[s] = 0;
for (int i = 1; i <= n; i++)
{
//首先找到最小的还未被访问的顶点标号
int u = -1, MIN = INF;
for (int j = 1; j <= n; j++)
{
if (vis[j] == 0 && d[j] < MIN)
{
u = j;
MIN = d[j];
}
}
if (u == -1) return;
vis[u] = 1;//记u被访问过
for (int j = 0; j < Adj[u].size(); j++)
{
int v = Adj[u][j].v;
if (vis[v] == 0)//枚举从U出发所有能到达的顶点v
{
if (d[u] + Adj[u][j].dis < d[v])
{
d[v] = d[u] + Adj[u][j].dis;//优化d[v]
pre[v] = u;
}
else if (d[u] + Adj[u][j].dis == d[v])
{
if (pre[v] > u)//如果原来的字典序比较大，就选字典序小的那个
pre[v] = u;
}
}
}
}
}
void DFS(int s, int v)
{
if (v == s)
{
printf("%d ", s);
return;
}
DFS(s, pre[v]);
printf("%d ", v);
}
int main()
{
while (scanf("%d %d %d %d", &n, &m, &s, &t) != EOF)
{
int temp;
int u, v;
for (int i = 1; i <= n; ++i)
Adj[i].clear();
for (int i = 0; i < m; i++)
{
scanf("%d%d%d", &u, &v, &temp);
Adj[u].push_back(Node(v, temp));
Adj[v].push_back(Node(u, temp));
}
//至此，初始化完成
Dijkstra(s);
if (d[t] != INF)
{
printf("%d\n", d[t]);//输出最短距离
DFS(s, t);
printf("\n");
}
else
printf("can't arrive\n");
}
return 0;
}
使用邻接矩阵做：
这题用邻接矩阵做有一个坑，就是要注意两个城市之间的道路不是唯一的，所以后面输入的距离会把前面的覆盖掉，应该进行比较，如果距离变小了，才可以覆盖
#define _CRT_SECURE_NO_WARNINGS 1
#include <cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxv = 1010;
const int INF = 1000000000;//无穷大
int n, m, s, t, G[maxv][maxv], pre[maxv];//记录前驱节点
//d[i]表示到点i的最短距离
int d[maxv];
int vis[maxv] = { 0 };
void Dijkstra(int s)
{
//初始化
fill(d, d + maxv, INF);//到所有点的距离都是无穷大
fill(vis, vis + maxv, 0);
for (int i = 1; i <= n; i++)
pre[i] = i;
d[s] = 0;
for (int i = 1; i <= n; i++)
{
//首先找到最小的还未被访问的顶点标号
int u = -1, MIN = INF;
for (int j = 1; j <= n; j++)
{
if (vis[j] == 0 && d[j] < MIN)
{
u = j;
MIN = d[j];
}
}
if (u == -1) return;
vis[u] = 1;//记u被访问过
for (int v = 1; v <= n; v++)
{
if (vis[v] == 0 && G[u][v] != INF)//枚举从U出发所有能到达的顶点v
{
if (d[u] + G[u][v] < d[v])
{
d[v] = d[u] + G[u][v];//优化d[v]
pre[v] = u;
}
else if (d[u] + G[u][v] == d[v])
{
if (pre[v] > d[u])
pre[v] = d[u];
}
}
}
}
}
void DFS(int s, int v)
{
if (v == s)
{
printf("%d ", s);
return;
}
DFS(s, pre[v]);
printf("%d ", v);
}
int main()
{
while (scanf("%d %d %d %d", &n, &m, &s, &t) != EOF)
{
int temp;
fill(G[0], G[0] + maxv * maxv, INF);//初始化邻接矩阵所有元素都为无穷大
int u, v;
for (int i = 0; i < m; i++)
{
scanf("%d%d%d", &u, &v, &temp);
if (temp < G[u][v])//小于当前距离的时候才能更新
G[u][v] = G[v][u] = temp;
}
//至此，初始化完成
Dijkstra(s);
if (d[t] != INF)
{
printf("%d\n", d[t]);//输出最短距离
DFS(s, t);
printf("\n");
}
else
printf("can't arrive\n");
}
return 0;
}
⭐⭐⭐问题 E: 最短路径问题
问题描述：给你n个点，m条无向边，每条边都有长度d和花费p，给你起点s终点t，要求输出起点到终点的最短距离及其花费，如果最短距离有多条路线，则输出花费最少的。
- 输入
输入n,m，点的编号是1~n,然后是m行，每行4个数 a,b,d,p，表示a和b之间有一条边，且其长度为d，花费为p。最后一行是两个数 s,t;起点s，终点t。n和m为0时输入结束。
(1<n<=1000, 0<m<100000, s != t)
- 输出
输出 一行有两个数， 最短距离及其花费。
- 样例输入
3 2
1 2 5 6
2 3 4 5
1 3
0 0
- 样例输出
9 11
本来以为这题两种解法，第一种纯D算法，第二种D算法+DFS，但是发现题目并没有说距离会是大于0的数，所以用SPFA算法比较好，可以判断负环，并且效率比D算法高！
下面用SPFA算法解题，另外最短路径的问题最好使用邻接表来存储，因为邻接矩阵的值是唯一的，有时候会涉及到判断的问题。
#include <cstdio>
#include <vector>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
const int maxn=1010;
const int INF=0x3fffffff;
bool inq[maxn];
int n,d[maxn],c[maxn],num[maxn];
struct node
{
int v,w,c;
node(int x,int y,int z):v(x),w(y),c(z){};
};
vector<node> adj[maxn];
bool SPFA(int s)
{
fill(d,d+maxn,INF);
memset(inq,0,sizeof(inq));
memset(num,0,sizeof(num));
fill(c,c+maxn,INF);
queue<int> q;
q.push(s);
inq[s]=true;
++num[s];
d[s]=0;
c[s]=0;
while(q.size())
{
int u=q.front();
q.pop();
inq[u]=false;
for(int i=0;i<adj[u].size();++i)
{
int v=adj[u][i].v;
int w=adj[u][i].w;
int t=adj[u][i].c;
if(d[u]+w<d[v])
{
d[v]=d[u]+w;
c[v]=c[u]+t;
if(!inq[v])
{
q.push(v);
inq[v]=true;
++num[v];
if(num[v]>=n)
return false;
}
}
else if(d[u]+w==d[v])
{
if(c[u]+t<c[v])
{
c[v]=c[u]+t;
}
}
}
}
return true;
}
int main()
{
int m,s,t,d1,d2,w,co;
while(~scanf("%d %d",&n,&m))
{
if(n==0)
break;
for(int i=1;i<=n;++i)
adj[i].clear();
for(int i=0;i<m;++i)
{
scanf("%d %d %d %d",&d1,&d2,&w,&co);
adj[d1].push_back(node(d2,w,co));
adj[d2].push_back(node(d1,w,co));
}
scanf("%d %d",&s,&t);
SPFA(s);
printf("%d %d\n",d[t],c[t]);
}
return 0;
}
总结
解决最短路径问题的方法有：
- Dij算法
- BF算法和SPFA算法
- Floyd算法
其中1、2都是解决单源最短路径问题的，F算法解决全源最短路径问题
在考虑图的存储时最好用邻接表，一是因为方便进行遍历，二是两个点之间不一定只有一条路，如果用邻接矩阵来存储会让后面的元素覆盖了前面的元素（避免这样的错误就需要额外的判断，比较麻烦）
用D算法求解的问题都可以用SPFA算法求解，两个算法在加入第二标尺后，思路也是一样的，但是要注意当需要统计最短路径条数时，BF算法每次都需要重新计算路径条数。
在使用最短路径算法的时候需要额外注意序号的下标，以及数组的初始化！
最短路径终于结束啦！撒花花
魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。
更多推荐
0
0- 0
已为社区贡献1条内容
所有评论(0)