当前位置: 代码迷 >> 综合 >> 四种最短路径算法(Dijkstra,Floyd,Bellman-fordspfa)
  详细解决方案

四种最短路径算法(Dijkstra,Floyd,Bellman-fordspfa)

热度:80   发布时间:2023-11-08 17:32:51.0

一.Dijkstra算法

如何理解Dijkstra算法

Dijkstrashi适用于权值非负的情况。

1.定义概览

Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法,在很多专业课程中都作为基本内容有详细的介绍,如数据结构,图论,运筹学等等。注意该算法要求图中不存在负权边。
问题描述:在无向图 G=(V,E) 中,假设每条边 E[i] 的长度为 w[i],找到由顶点 V0 到其余各点的最短路径。(单源最短路径)

2.算法描述

1)算法思想:设G=(V,E)是一个带权有向图,把图中顶点集合V分成两组,第一组为已求出最短路径的顶点集合(用S表示,初始时S中只有一个源点,以后每求得一条最短路径 , 就将加入到集合S中,直到全部顶点都加入到S中,算法就结束了),第二组为其余未确定最短路径的顶点集合(用U表示),按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中,总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外,每个顶点对应一个距离,S中的顶点的距离就是从v到此顶点的最短路径长度,U中的顶点的距离,是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。
2)算法步骤:
a.初始时,S只包含源点,即S={v},v的距离为0。U包含除v外的其他顶点,即:U={其余顶点},若v与U中顶点u有边,则

3.其他

Dijkstra完全类似于prim算法生成最小生成树。

4.代码实现

int dijkstra(int n)
{//初始化v[0]到v[i]的距离for(int i=1;i<=n;i++)dis[i] = w[0][i];                                       vis[0]=1;//标记v[0]点for(int i = 1; i <= n; i++){//查找最近点int min = INF,k = 0;for(int j = 0; j <= n; j++)if(!vis[j] && dis[j] < min)min = dis[j],k = j;vis[k] = 1;//标记查找到的最近点//判断是直接v[0]连接v[j]短,还是经过v[k]连接v[j]更短for(int j = 1; j <= n; j++)if(!vis[j] && min+w[k][j] < dis[j])d[j] = min+w[k][j];}return dis[j];
}

二.Floyed算法

floyd算法可以有负权值的边,但不能有包含负权值边组成的回路
参考网页:http://www.cnblogs.com/rain-1/p/5033505.html
Floyed算法(实际是动态规划问题)
  问题:权值矩阵matrix[i][j]表示i到j的距离,如果没有路径则为无穷
     求出权值矩阵中任意两点间的最短距离
  分析:对于每一对定点u,v看是否存在一个点w使从u到w再到v的路径长度比已知路径短
  如果有则更新从u到w的距离
  
  1:不用状态压缩的动态规划算法:
    状态定义:d[1][i][j]表示以1作为媒介时从i到j的最短距离
         d[2][i][j]表示以1,2中的点作为媒介时从i到j的最短距离
         ……
        d[n][i][j]表示以1,2, ……n中的点作为媒介时从i到j的最短距离
  状态转移方程d[k][i][j] = min(d[k-1][i][j], d[k-1][i][j]+d[k-1][k][j]);
        理解为把i到j的路径氛围两种情况,一种不经过k,一种经过k

  2:状态压缩表示:
    假设用d[i][j]表示从i到j的最短路径
    由于d[i][j]在计算中重复使用,因此表示阶段的那一维被取消了
    在没有计算出来新的d[i][j]的时候d[i][j]存储的实际是d[k-1][i][j]的值
    因此可以省去表示阶段的那一维
    状态转移方程:d[i][j] = min(d[i][j], d[i][k]+d[k][j]);

3.代码实现

状态压缩的Ffloyed

/* 本程序中节点标号1,2,……nfloyed算法:floyed算法实际上是动态规划,对于任意两个点u,v,看是否存在一个点w,使得从u到w再到v的距离比从u直接到v的距离短d[i][j]存储从i点到j点的最短距离 */
#define M 100
#define INF 0x3f3f3f
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
int mat[M][M];
int n, m;
void FloyedOrginal()
{//用k遍历所有中间节点的可能for(int k = 1; k <= n; k++)for(int i = 1; i <= n; i++)for(int j = 1; j <= n; j++)mat[i][j] = min(mat[i][j], mat[i][k]+mat[k][j]);//是否经过k
}
void Init()
{printf("请输入节点的个数\n");scanf("%d", &n);printf("请输入已知数据的组数\n");scanf("%d", &m);for(int i = 0; i <= n; i++)for(int j = 0; j <= n; j++)mat[i][j] = INF;for(int i = 0; i < m; i++){int u, v, w;scanf("%d%d%d", &u, &v, &w);mat[u][v] = mat[v][u] = w;}
}
int main()
{Init();FloyedOrginal();printf("%d", mat[1][4]);return 0;
}

三.Bellman-ford算法

Bellman_ford可以计算存在负权边的情况

bellman-ford算法进行n-1次更新(一次更新是指用所有节点进行一次松弛操作)来找到到所有节点的单源最短路。bellman-ford算法和dijkstra其实有点相似,该算法能够保证每更新一次都能确定一个节点的最短路,但与dijkstra不同的是,并不知道是那个节点的最短路被确定了,只是知道比上次多确定一个,这样进行n-1次更新后所有节点的最短路都确定了(源点的距离本来就是确定的)。
现在来说明为什么每次更新都能多找到一个能确定最短路的节点:
1.将所有节点分为两类:已知最短距离的节点和剩余节点。
2.这两类节点满足这样的性质:已知最短距离的节点的最短距离值都比剩余节点的最短路值小。(这一点也和dijkstra一样)
3.有了上面两点说明,易知到剩余节点的路径一定会经过已知节点
4.而从已知节点连到剩余节点的所有边中的最小的那个边,这条边所更新后的剩余节点就一定是确定的最短距离,从而就多找到了一个能确定最短距离的节点,不用知道它到底是哪个节点。

bellman-ford的一个优势是可以用来判断是否存在负环,在不存在负环的情况下,进行了n-1次所有边的更新操作后每个节点的最短距离都确定了,再用所有边去更新一次不会改变结果。而如果存在负环,最后再更新一次会改变结果。原因是之前是假定了起点的最短距离是确定的并且是最短的,而又负环的情况下这个假设不再成立。

Bellman-ford的实现代码:

#include <stdio.h>
int main()
{int dis[10],n,m,u[10],v[10],w[10];int inf=99999999;scanf("%d %d",&n,&m);//输入点数和边数for(int i=1; i<=m; i++)scanf("%d %d %d",&u[i],&v[i],&w[i]);//输入两条边和距离for(int i=1; i<=n; i++)//初始化一号顶点到其余各个顶点的路程dis[i]=inf;dis[1]=0;//初始化点1到自己的距离为0for(int k=1; k<=n-1; k++)//Bellman核心算法语句,最多运行n-1次{int check=0;for(int i=1; i<=m; i++){if(dis[v[i]] > dis[u[i]]+w[i]){dis[v[i]] = dis[u[i]]+w[i];check = 1;}}if(check == 0)  break;//由于最多运行n-1次,所以一旦全部松弛完毕就直接跳出}for(int i=1; i<=n; i++)printf("%d ",dis[i]);return 0;
}

Bellman_ford效率太低,spfa是对它的优化。

四:spfa算法

1.详细讲解:http://www.360doc.com/content/13/1208/22/14357424_335569176.shtml

2.SPFA 在形式上和广度(宽度)优先搜索非常类似,不同的是bfs中一个点出了队列就不可能重新进入队列,但是SPFA中一个点可能在出队列之后再次被放入队列,也就是一个点改进过其它的点之后,过了一段时间可能本身被改进(重新入队),于是再次用来改进其它的点,这样反复迭代下去。

void  spfa(s);  //求单源点s到其它各顶点的最短距离for i=1 to n do { dis[i]=∞; vis[i]=false; }   //初始化每点到s的距离,不在队列dis[s]=0;  //将dis[源点]设为0vis[s]=true; //源点s入队列head=0; tail=1; q[tail]=s; //源点s入队, 头尾指针赋初值while head<tail do {head+1;  //队首出队v=q[head];  //队首结点vvis[v]=false;  //释放对v的标记,可以重新入队for 每条边(v,i)  //对于与队首v相连的每一条边if (dis[i]>dis[v]+a[v][i])  //如果不满足三角形性质dis[i] = dis[v] + a[v][i]   //松弛dis[i]if (vis[i]=false) {tail+1; q[tail]=i; vis[i]=true;} //不在队列,则加入队列}