欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Dijkstra算法---单源最短路径

程序员文章站 2024-03-16 14:00:28
...

本文是对《啊哈!算法》学习过程的记录与总结。

最短路径算法对比分析

Floyd Dirjkstra Bellman-Ford 队列优化的Bellman-Ford
空间复杂度 O(N**2) O(M) O(M) O(M)
时间复杂度 O(N**3) O((M+N)log N) O(NM) 最坏情况:O(NM)
使用情况 稠密图和顶点关系密切 稠密图和顶点关系密切 稀疏图和边关系密切 稀疏图和边关系密切
负权 可以解决负权 不能解决负权 可以解决负权 可以解决负权
有负权边 可以处理 不能处理 可以处理 可以处理
判定是否存在负权回路 不能 不能 可以判定 可以判定

Dirjkstra(迪科斯彻)算法使用了广度优先搜索解决赋权单源最短路径问题,最大的弊端是它无法处理带有负权边以及负权回路的图,但它具有良好的可扩展性,扩展后可以适应很多问题。另外用堆优化的Dijkstra算法的时间复杂度可以达到(MlogN)。
算法的思路:

1、将所有的顶点分为两部分:已知最短路径的顶点集合P和未知最短路径的顶点集合Q。最开始,已知最短路径的顶点集合P中只有源点一个顶点。我们这里用一个book数组来记录哪些点在集合P中。

2、设置源点s到自己的最短路径为0(dis[0]=0),若存在有源点能直接到达的顶点i,则把dis[i]设为e[s][i] , 同时把其他所有(源点不能直接到达的)顶点的最短路径设为INF。

3、在集合Q的所有顶点中选择一个离源点s最近的顶点u(即dis[u]最小),加入到集合P。并考察所有以点u为起点的边,对每一条边进行松弛操作。

4、重复第3步,如果集合Q为空,算法结束。最终dis数组中的值就是源点到所有顶点的最短路径。

重点:

1、在未被确定最短路径的点中 找出离原点最近的点u(此时dis[u]从“估计值”变成“确定值”)

2、对点i的所有出边进行松弛


Dijkstra算法---单源最短路径

求出每个顶点与源点(1)的最短距离

要求输入:

6 9

1 2 1

1 3 12

2 3 9

2 4 3

3 5 5

4 3 4

4 5 13

4 6 15

5 6 4

要求输出:

0 1 8 4 13 17

//Dijkstra算法
#include<iostream>
#define INF 99999999
int main()
{
	int e[6][6], dis[6], book[6] = {0},i, j, u, m, n, a, b, c,min;
	//输入城市个数,道路个数
	std::cin >> n >> m; 

	//初始化道路信息
	for (i = 1; i <= n; i++)
		for (j = 1; j <= n; j++)
			if (i == j)
				e[i][j] = 0;
			else
				e[i][j] =INF;

	//导入道路信息
	for (i = 1; i <= m; i++)
	{
		std::cin >> a >> b >> c;
		e[a][b] = c;
	}

	for (i = 1; i <= n; i++)
		dis[i] = e[1][i];

	//第一个城市
	book[1] = 1;
	
	//算法核心:循环松弛,n个数,1不需要,所以是n-1次循环
	for (i = 1; i <= n-1; i++) 
	{
		//先找出距离源点最短的点
		min = INF;
		for (j = 2; j <= n; j++)
		{
			if (dis[j] < min && book[j]==0)
			{
				min = dis[j];
				//用u记录里源点最近的点
				u = j;
			}
		}
		//u从估计值变成确定值
		book[u] = 1;
		for (j = 1; j <= n; j++)
			if(e[u][j]<INF && dis[j]>dis[u]+e[u][j])
				{
					dis[j] = dis[u] + e[u][j];

				}
	}

	//输出
	for (i = 1; i <= n; i++)
		std::cout << dis[i] << " ";
	system("pause")
	return 0;
}