本文共 2617 字,大约阅读时间需要 8 分钟。
1、Bellman-Ford算法
2、Dijkstra算法(代码 以邻接矩阵为例) && Dijkstra + 优先队列的优化(也就是堆优化)
3、floyd-Warshall算法(代码 以邻接矩阵为例)
4、SPFA(代码 以前向星为例)
5、BFS 求解最短路
6、路径还原
参考文章
1.Bellman - Ford 算法:const int INF = 1000;const int MAXN =10000;const int MAXE =100000;int dist[MAXN + 3];//dist[i]表示点 i 到源点的最短距离int head[MAXN + 3];//链式前向星用于存图struct NODE { int to; int w; int next; };NODE edge[MAXE + 3];bool BellmanFord(int n, int s) { // s 为源点 for(int i = 0; i <= n; i++) dist[i] = INF;//初始化 dist[s] = 0; for(int i = 0; i < n - 1; i++) { //对于所有边循环 n - 1,即尝试松弛 n - 1 次 for(int j = 1; j <= n; j++) { //选取一个起点 if(dist[j] == INF) continue; for(int k = head[j]; k != -1; k = edge[k].next) { //遍历从当前起点出发的所有边,并尝试进行松弛 if(edge[k].w != INF && dist[edge[k].to] > dist[j] + edge[k].w) { //进行松弛操作 dist[edge[k].to] = dist[j] + edge[k].w; } } } } for(int j = 1; j <= n; j++) { //进行第 n 次松弛 判断是否存在负环 for(int k = head[j]; k != -1; k = edge[k].next) { //存在负环返回 false if(edge[k].w != INF && dist[edge[k].to] > dist[j] + edge[k].w) return false; } } return true;}
2.Dijkstra算法
const int INF = INT_MAX;const int MAXN =10000;int mmap[MAXN + 3][MAXN + 3];//记录图的信息int dist[MAXN + 3];//dist[i]表示点 i 到源点的最短距离int pre[MAXN + 3];//记录前趋 记录最短路径bool setA[MAXN + 3];//是否属于集合A,集合A代表着已经确定最短路径的点集void Dijkstra(int n, int s) { // s 为源点 for(int i = 1; i <= n; i++) { //初始化 setA[i] = false; if(i != s) { dist[i] = mmap[s][i]; pre[i] = s; } } dist[s] = 0, setA[s] = true; for(int i = 1; i <= n - 1; i++) { //求 s 到其他 n - 1个节点的最短路径 int minn = INF; int k = 0; for(int j = 1; j <= n; j++) { // 在属于集合 Vb 的点中取一点, 满足 s 到其的距离最小 if(!setA[j] && dist[j] < minn) { minn = dist[j], k = j; } } if(!k) return; // 没有点可以扩展,即剩余的点不可达,则结束算法 setA[k] = true; //将新找的点从集合 Vb 中除去, 加入集合 Va for(int j = 1; j <= n; j++) { //对于每个与 k 相邻 且属于 Vb 的点,更新 s 到 j 的最短路径 if(!setA[j] && mmap[k][j] != INF && dist[j] > dist[k] + mmap[k][j]) { dist[j] = dist[k] + mmap[k][j]; pre[j] = k; } } }}
3.关于松弛问题的解释
松弛(relaxation):指对于图 G = (V, E) 中 每个顶点v ∈ V,都设置一个属性dist[v],用来描述从源点s到v的最短路径上权值的上界.在开始进行一个最短路径算法时,只知道图中边和权值.随着算法的进行,逐渐得到各对顶点的最短路径的信息.算法会逐渐更新这些信息,每步都会检查是否可以找到一条路径比当前给定路径更短.这一过程通常称为松弛.下面这两张图即为对边
Relax( u, v, W ) {//W 代表边 的权值 if ( dist[v] > dist[u] + W ) { dist[v] = dist[u] + W ; }}
转载地址:http://sqqpi.baihongyu.com/