三种求最短路算法基本描述及实现

比较：

	Floyed	Dijkstra(优先队列优化)	SPFA(优先队列优化)
时间复杂度	o(n^3)	o(n+m)(logm)	o(km)
基本思想	动态规划	贪心	贪心
适用范围	无负环图	无负权图	无负环图
	多源最短路	不含负权图的低复杂度解	含负权边时的单源最短路求解

1.Floyed算法 变量声明：

n，N        点的数量

m， M        边的数量

G[ x ][ y ]        图，表示从 x 点到 y 点的边的权值

dis[ i ][ j ]        路径，表示当前情况下 i 点到 j 点的最短路径长度

算法简洁描述：

通过不断选取中间点来更新从点 i 到点 j 的最短路径

更新方式：

将现有的点 i 到 j 的最短距离 与 已知点 i 到中间点 k 的最小距离 + k 到 j 的路径距离 进行比较

公式表述：

dis[ i ][ j ] = min( dis[ i ][ j ] ,  dis[ i ][ k ] + G[ k ][ j ] )

循环次序：

for temp in spot:
    for start in spot:
        for end in spot:

基本实现： 目标：

读入一个含有n条边的无负环无向图，求出图中任意两点之间的最短路径

代码：

#include 
using namespace std;
//n->点数 m->边数 
#define N 1000
#define M 2000
int n, m;
//邻接矩阵图数组 
int G[N+1][N+1];
//最短路数组 
int dis[N+1][N+1];
//算法内容 
void Floyed()
{
	for(int k = 1; k <= n; k++){	//中间点 
	for(int i = 1; i <= n; i++){	//起始点 
        if(i == k) continue;
	for(int j = 1; j <= n; j++){	//末尾点 
		if(i == j) continue;
        dis[i][j] = min(dis[i][j], dis[i][k] + G[k][j]); 
	}
	}
	}	
}

int main(void)
{
	memset(dis, 0x3f, sizeof(dis));
	scanf("%d%d", &n, &m);
	//读入无负环无向图 
	for(int i = 1; i <= m; i++){
		int x, y, v;
		scanf("%d%d%d", &x, &y, &v);
		G[x][y] = G[y][x] = v;
	}
	Floyed();
	return 0;
}

---

2.Dijkstra算法 变量声明：

n, N       图的点
m, M      图的边

start       起始点

INF        无穷大
链式前向星edge      x 点下标, v 边权值, next 连接点
vis[ i ]         标记从起始点到点 i 的最短路径是否已经更新
dis[ i ]         表示从起始点到点 i 的最短路径值
结构体 ty        收纳点信息，包括点下标 x 和最短路径值 dis
priority_queueq;       边权升序排列的优先队列

算法简洁描述：

以既定起点的最短路径值为 0 开始，不断地从当前已确定最短路径的点中选取dis值最小的点，用选取点去更新所有相邻点的最短路径

过程描述：

1.更新起始点 dis 为 0，将起始点的信息(下标 和 dis值) 放进优先队列

2.从优先队列中取出一个未用于更新且 dis 值最小的点信息，然后将该点信息丢出队列

3.用取出的点去更新邻近点的 dis 值，并将新更新的点的信息放进优先队列

4.重复2、3 *** 作，直到优先队列元素为空

其实如果利用优先队列优化，而且每个队列元素拿出来用完就丢掉，就不需要判断取出的点是否曾用于更新，这里为了突出这个先决条件，特意声明

简单实例模拟(变量意义看上述)：

 现在求从点 1 到各点的最短路径值：

1

2

3

4

5

6

7

8

dis[1]

vis[1]

dis[2]

vis[2]

dis[3]

vis[3]

dis[4]

vis[4]

dis[5]

vis[5]

dis[6]

vis[6]

dis[7]

vis[7]

dis[8]

vis[8]

初始化更新

起点的dis值为0，其余dis值为INF，起点最短路径已确定，vis为true

0

T

INF

F

INF

F

INF

F

INF

F

INF

F

INF

F

INF

F

第一次更新

与起点邻接的点有3、4、2，更新dis，vis

0

T

0+6

T

0+5

T

0+2

T

INF

F

INF

F

INF

F

INF

F

第二次更新

在已经更新的点中选取dis最小且未用于更新最短路的点4作为新的起点，更新所有能更新的最短路径，这次只有点5可更新

0

T

6

T

4

T

2

T

2+4

T

INF

F

INF

F

INF

F

第三次更新

选取已经更新的点中dis值最小且未用于更新最短路的点3作为起点，更新最短路

0

T

6

T

4

T

2

T

6

T

4+5

T

4+6

T

INF

F

第四次更新

继续按上述方式选点，出现dis相同的两点，发现选择点2已经不能更新，所以选择点5

0

T

6

T

4

T

2

T

6

T

9

T

10

T

6+7

T

与计算机跑出的结果相同：

基本实现： 目标：

读入一个含有 n 个点的无负权无向图，求出图中从起始点 start 到任意点的最短路径

代码：

#include
using namespace std;
//边&点 
#define N 100000
#define M 200000
int n, m, start;
//链式前向星存图 
int cnt = 0, head[M+1];
struct Node{
	int x, v, next;
}edge[2*N+1];
void addedge(int x, int y, int v)
{
	edge[++cnt].v = v;
	edge[cnt].x = y;
	edge[cnt].next = head[x];
	head[x] = cnt;
}
//
int dis[N+1];
bool vis[N+1];
struct ty{
	int dis, x;
	bool operator < (const ty &a) const{
		return dis > a.dis;
	} 
}temp;
priority_queueq;
//Dijkstra算法
void Dijkstra(int st)
{
    //将初始点信息放进队列
	dis[st] = 0;
    temp.dis = 0; temp.x = st;
    q.push(temp);
    //
	while(!q.empty())
	{
        //找到当前队列中边权最小点
		temp = q.top(); q.pop();
        int x = temp.x;
        if(vis[x]) continue;
        vis[x] = true;
        //利用取出的点更新最短路
        for(int i = head[x]; i != -1; i = edge[i].next){
            int node = edge[i].x;
			//将可更新点更新，并放进队列
            if(dis[node] > dis[x] + edge[i].v){
                dis[node] = dis[x] + edge[i].v;
                ty ne;
                ne.dis = dis[node]; ne.x = node;
                q.push(ne);
            }
        }
	}
} 

int main(void)
{
	memset(head, -1, sizeof(head));
	memset(dis, 0x3f, sizeof(dis));
	memset(vis, false, sizeof(vis));
	//存图
    scanf("%d%d", &n, &m);
	for(int i = 1; i <= m; i++){
		int x, y, v;
		scanf("%d%d%d", &x, &y, &v);
		addedge(x, y, v);
		addedge(y, x, v);
	}	
	scanf("%d", &start); 
	Dijkstra(start);
	return 0;
} 

---

3.SPFA算法 变量声明

n, N       图的点
m, M      图的边

start       起始点
链式前向星edge      x 点下标, v 边权值, next 连接点
vis[ i ]         标记从起始点到点 i 的最短路径是否已经更新
dis[ i ]         表示从起始点到点 i 的最短路径值
queueq;       存放点下标的队列

简洁描述：

SPFA思路和过程都和Dijkstra相似，不同的是SPFA不会去研究被用于更新最短路的点dis值是否是最小的

过程描述：

1.更新起始点 dis 为 0，放进队列

2.从队列中取出一个点

3.用取出的点更新所有与其相邻的点的 dis 。并且，如果当前队列中没有新更新过的点，就将新更新的点放进队列

4.重复2、3 *** 作，直到队列为空

基本实现： 目标:

读入一个含有 n 个点的无负权无向图，求出图中从起始点 start 到任意点的最短路径

代码:

#include
using namespace std;
//边&点 
#define N 100000
#define M 200000
int n, m, start;
//链式前向星存图 
int cnt = 0, head[M+1];
struct Node{
	int x, v, next;
}edge[2*N+1];
void addedge(int x, int y, int v)
{
	edge[++cnt].v = v;
	edge[cnt].x = y;
	edge[cnt].next = head[x];
	head[x] = cnt;
}
//
int dis[N+1];
bool vis[N+1];
queueq;
//SPFA
void spfa(int st)
{
	//起点初始化，放进队列 
	dis[st] = 0; vis[st] = 1;
	q.push(st);
	while(!q.empty())
	{
		//拿出队首元素 
		int x = q.front(); q.pop();
		vis[x] = false;
		//更新最短路径值 
		for(int i = head[x]; i != -1; i = edge[i].next){
			int ne = edge[i].x;
			if(dis[ne] > dis[x] + edge[i].v){
				dis[ne] = dis[x] + edge[i].v;
				//如果该元素现在不在队列，放进队列 
				if(!vis[ne]){
					q.push(ne);
					vis[ne] = true;
				}
			}
		}
	}
} 
int main(void)
{
	memset(dis, 0x3f, sizeof(dis));
	memset(vis, false, sizeof(vis));
	memset(head, -1, sizeof(head));
	//存图
    scanf("%d%d", &n, &m);
	for(int i = 1; i <= m; i++){
		int x, y, v;
		scanf("%d%d%d", &x, &y, &v);
		addedge(x, y, v);
		addedge(y, x, v);
	}	
	scanf("%d", &start); 
	spfa(start);
	//输出计算结果 
	for(int i = 1; i <= n; i++){
		printf("dis %d: %2d    ", i, dis[i]);
		if(i %2 == 0) cout <

欢迎分享，转载请注明来源：内存溢出

原文地址: https://outofmemory.cn/langs/798405.html