脚本宝典收集整理的这篇文章主要介绍了图论━━最短路问题,脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
图论中的最短路问题,求两个点之间最短距离(路径)的问题;
规定使用n
: 表示点的数量;m
: 表示边的数量;边数m
是顶点数n
的平方级别视为稠密图
算法总结:
求从一个点到其他所有点的最短距离,顶点为1,2,3...n
,求顶点1
到其他所有顶点的最短路
Dijkstra基于贪心算法
稠密图使用邻接矩阵存储
边权是正数时,如果数据出现自环和重边需要预处理:
距离都是单源点1号点到其他点的距离,使用dist[N]数组保存当前距离;维护一个已经确定最小距离的点的集合S,使用了st[N]数组来标记:
算法思路:
1. 初始化距离 dist[1]=0, dist[i]=infity
2. for i: 1~n:
t <-- 不在S中的点,且距离最近的点
S <-- t(将t加入到S中)
用点t来更新其他点的距离
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 510;
int n, m;
int g[N][N]; // 邻接矩阵
int dist[N]; // 当前顶点1到所有点的距离
bool st[N]; // 是否加入集合S(已知最短距离的点集合)
int dijkstra()
{
// 初始化当前的距离
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
for (int i = 0; i < n; i++)
{
int t = -1;
for (int j = 1; j <= n; j++)
if (!st[j] && (t == -1 || dist[t] > dist[j]))
t = j;
st[t] = true;
// 更新相邻顶点的距离
for (int j = 1; j <= n; j++)
dist[j] = min(dist[j], dist[t] + g[t][j]);
}
//判断dist[n]
if (dist[n] == 0x3f3f3f3f)
return -1;
return dist[n];
}
int main()
{
scanf("%d%d", &n, &m);
memset(g, 0x3f, sizeof g);
while (m--)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
// 处理多重边
g[a][b] = min(g[a][b], c);
}
int t = dijkstra();
printf("%dn", t);
}
稀疏图--使用邻接表存储,方便遍历邻接边,h[N],w[N],e[N],ne[N]
采用stl的priority_queue<PII, vector<PII>, greater<PII>> queue;
Bellman-Ford算法 O(nm) SPFA 一般:O(m),最坏O(nm); 是Bellman-Ford算法的一个优化, 效率比Bellman-Ford好
但是不是所有的问题都可以用SPFA做,例如 最短路边数<=k的最短路,只能使用Bellman-Ford算法
边的存储方式:只要能够遍历所有的边就可以;
struct edge{
int a,b,w;
}edges[N];
for 1:n :
for 所有边 a,b,w (a -w-> b)
dist[b]=min(dist[b], dist[a]+w(a,b));
思想:因为最短路径 最多为n-1个边 的组合;
松弛n-1次,一定可以松弛完最远的点,得到所有的最短距离
注意: 每次迭代,是对同一个状态进行迭代的,对相同的距离状态进行更新(备份)
说明
一般是O(m),网格图可能卡成O(nm)
对Bellman-Ford算法的改进, 只有点a变小了,才有可能更新邻点的距离
使用一个队列,存储所有距离变小的点a
起点和终点都不确定,都任意
Floyd算法 O(n^3) ---基于动态规划原理
都使用有向图来建图,无向图建立2条双向边即可
稠密图使用邻接矩阵g[N][N]存储边;稀疏图使用邻接表,h[N], e[N],ne[N],idx
有负权回路的图,不一定存在最短路,负环不在路径上也可能求到某点的最短路径
* 使用邻接矩阵存储 d[N][N]
;
以上是脚本宝典为你收集整理的图论━━最短路问题全部内容,希望文章能够帮你解决图论━━最短路问题所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。