首页 > 代码库 > HDU - 2544 - 最短路 (最基础单源最短路问题!!dijkstra+floyd+SPFA)

HDU - 2544 - 最短路 (最基础单源最短路问题!!dijkstra+floyd+SPFA)

最短路

Time Limit: 5000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 34617    Accepted Submission(s): 15001


Problem Description
在每年的校赛里,所有进入决赛的同学都会获得一件很漂亮的t-shirt。但是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候,却是非常累的!所以现在他们想要寻找最短的从商店到赛场的路线,你可以帮助他们吗?

 

Input
输入包括多组数据。每组数据第一行是两个整数N、M(N<=100,M<=10000),N表示成都的大街上有几个路口,标号为1的路口是商店所在地,标号为N的路口是赛场所在地,M则表示在成都有几条路。N=M=0表示输入结束。接下来M行,每行包括3个整数A,B,C(1<=A,B<=N,1<=C<=1000),表示在路口A与路口B之间有一条路,我们的工作人员需要C分钟的时间走过这条路。
输入保证至少存在1条商店到赛场的路线。
 

Output
对于每组输入,输出一行,表示工作人员从商店走到赛场的最短时间
 

Sample Input
2 1 1 2 3 3 3 1 2 5 2 3 5 3 1 2 0 0
 

Sample Output
3 2
 

Source
UESTC 6th Programming Contest Online
 


dijkstra:

按路径长度递增次序产生算法:
把顶点集合V分成两组:
(1)S:已求出的顶点的集合(初始时只含有源点V0)
(2)V-S=T:尚未确定的顶点集合
将T中顶点按递增的次序加入到S中,保证:
(1)从源点V0到S中其他各顶点的长度都不大于从V0到T中任何顶点的最短路径长度
(2)每个顶点对应一个距离值
S中顶点:从V0到此顶点的长度
T中顶点:从V0到此顶点的只包括S中顶点作中间顶点的最短路径长度
依据:可以证明V0到T中顶点Vk的,或是从V0到Vk的直接路径的权值;或是从V0经S中顶点到Vk的路径权值之和
(反证法可证)
求最短路径步骤
算法步骤如下:
G={V,E}
1. 初始时令 S={V0},T=V-S={其余顶点},T中顶点对应的距离值
若存在<V0,Vi>,d(V0,Vi)为<V0,Vi>弧上的权值
若不存在<V0,Vi>,d(V0,Vi)为∞
2. 从T中选取一个与S中顶点有关联边且权值最小的顶点W,加入到S中
3. 对其余T中顶点的距离值进行修改:若加进W作中间顶点,从V0到Vi的距离值缩短,则修改此距离值
重复上述步骤2、3,直到S中包含所有顶点,即W=Vi为止

dijkstra确实和最小生成树的prim很像!!


dijkstra+floyd+SPFA(简介):

Bellman-Ford:

求单源最短路,可以判断有无负权回路(若有,则不存在最短路), 时效性较好,时间复杂度O(VE)。

Bellman-Ford算法是求解单源最短路径问题的一种算法。

      单源点的最短路径问题是指: 给定一个加权有向图G和源点s,对于图G中的任意一点v,求从s到v的最短路径。

      与Dijkstra算法不同的是,在Bellman-Ford算法中,边的权值可以为负数。       设想从我们可以从图中找到一个环路(即从v出发,经过若干个点之后又回到v)且这个环路中所有边的权值之和为负。那么通过这个环路,环路中任意两点的最短路径就可以无穷小下去。如果不处理这个负环路,程序就会永远运行下去。 而Bellman-Ford算法具有分辨这种负环路的能力。

Dijkstra:

求单源、无负权的最短路。时效性较好,时间复杂度为O(V*V+E)。 源点可达的话,O(V*lgV+E*lgV)=>O(E*lgV)。       当是稀疏图的情况时,此时E=V*V/lgV,所以算法的时间复杂度可为 O(V^2)  。若是斐波那契堆作优先队列的话,算法时间复杂度,则为O(V*lgV + E)。 

Floyd:

求多源、无负权边的最短路。用矩阵记录图。时效性较差,时间复杂度O(V^3)。        Floyd-Warshall算法(Floyd-Warshall algorithm)是解决任意两点间的最短路径的一种算法,可以正确处理有向图或负权的最短路径问题。

Floyd-Warshall算法的时间复杂度为O(N^3),空间复杂度为O(N^2)。

      Floyd-Warshall的原理是动态规划: 设Di,j,k为从i到j的只以(1..k)集合中的节点为中间节点的最短路径的长度。 若最短路径经过点k,则Di,j,k = Di,k,k-1 + Dk,j,k-1;  若最短路径不经过点k,则Di,j,k = Di,j,k-1。  因此,Di,j,k = min(Di,k,k-1 + Dk,j,k-1 , Di,j,k-1)。

      在实际算法中,为了节约空间,可以直接在原来空间上进行迭代,这样空间可降至二维。 Floyd-Warshall算法的描述如下: for k ← 1 to n do   for i ← 1 to n do     for j ← 1 to n do       if (Di,k + Dk,j < Di,j) then         Di,j ← Di,k + Dk,j; 其中Di,j表示由点i到点j的代价,当Di,j为 ∞ 表示两点之间没有任何连接。

后来,我看Bellman-Ford的队列优化,SPFA( Shortest Path Faster Algorithm   )。

SPFA:

是Bellman-Ford的队列优化,时效性相对好,时间复杂度O(kE)。(k<<V)。

与Bellman-ford算法类似,SPFA算法采用一系列的松弛操作以得到从某一个节点出发到达图中其它所有节点的最短路径。所不同的是,SPFA算法通过 维护一个队列 ,使得一个节点的当前最短路径被更新之后没有必要立刻去更新其他的节点,从而大大减少了重复的操作次数。

      SPFA算法可以用于存在负数边权的图,这与dijkstra算法是不同的。

与Dijkstra算法与Bellman-ford算法  不同,SPFA的算法时间效率是不稳定的,即它对于不同的图所需要的时间有很大的差别。

      在最好情形下,每一个节点都只入队一次,则算法实际上变为广度优先遍历,其时间复杂度仅为O(E)。另一方面,存在这样的例子,使得每一个节点都被入队(V-1)次,此时算法退化为Bellman-ford算法,其时间复杂度为O(VE)。

      SPFA算法在负边权图上可以完全取代Bellman-ford算法,另外在稀疏图中也表现良好。但是在非负边权图中,为了避免最坏情况的出现,通常使用效率更加稳定的Dijkstra算法,以及它的使用堆优化的版本。通常的SPFA算法在一类网格图中的表现不尽如人意。




AC代码1(dijkstra):

#include <cstdio>
#include <cstring>
#include <algorithm>
#define INF 0x7f7f7f7f
using namespace std;

const int N = 105;
int map[N][N], vis[N], dis[N];
int n, m;

void dijk()
{
	for(int i=1; i<=n; i++) dis[i] = INF;
	dis[1] = 0;
	for(int i=1; i<=n; i++)
	{
		int min = INF, pos;
		for(int j = 1; j<=n; j++)
			if(!vis[j] && dis[j] < min) 
				min = dis[pos = j];
		vis[pos] = 1;
		for(int j=1; j<=n; j++)
			if(!vis[j] && dis[pos] + map[pos][j] < dis[j])
				dis[j] = dis[pos] + map[pos][j];
	}
}

int main()
{
	while(scanf("%d %d", &n, &m) == 2 && n||m)
	{
		memset(vis, 0, sizeof(vis));
		memset(map, 0x7f, sizeof(map));
		while(m--)
		{
			int x, y, w;
			scanf("%d %d %d", &x, &y, &w);
			if(w < map[x][y]) map[x][y] = map[y][x] = w;
		}
		dijk();
		printf("%d\n", dis[n]);
	}
	return 0;
}


AC代码2(floyd):

#include <cstdio>
#include <cstring>
#include <algorithm>
#define INF 0x3f3f3f3f			//这里不能开太大,如果开0x7f7f7f7f的话下面那里可能会越界 
using namespace std;

const int MAX = 105;
int map[MAX][MAX];
int n, m;

void floyd()
{
	for(int k=1; k <= n; k++)
		for(int i=1; i<=n; i++)
			for(int j=1; j<=n; j++)
				if(map[i][k] + map[k][j] < map[i][j])		//这里可能会越界 
					map[i][j] = map[i][k] + map[k][j];
}

int main()
{
	while(scanf("%d %d", &n, &m) == 2 && n||m)
	{
		memset(map, 0x3f, sizeof(map));
		while(m--)
		{
			int x, y, w;
			scanf("%d %d %d", &x, &y, &w);
			if(w < map[x][y]) map[x][y] = map[y][x] = w;
		}
		floyd();
		printf("%d\n", map[1][n]);
	}
	return 0;
} 


AC代码3(SPFA):

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define INF 0x3f3f3f3f
using namespace std;

const int MAX = 105;
int map[MAX][MAX], dis[MAX], vis[MAX];
int n, m;

void spfa(int s)
{
	int pos;
	dis[s] = 0;
	queue<int> q;
	q.push(s);
	vis[s] = 1;
	while(!q.empty())
	{
		pos = q.front(); q.pop();
		vis[pos] = 0;
		for(int i=1; i<=n; i++)
		{
			if(dis[pos] + map[pos][i] < dis[i])
			{
				dis[i] = dis[pos] + map[pos][i];
				if(vis[i] == 0)
				{
					q.push(i);
					vis[i] = 1;
				}
			}
		}
	}
}

int main()
{
	while(scanf("%d %d", &n, &m)==2 && n||m)
	{
		memset(vis, 0, sizeof(vis));
		memset(map, 0x3f, sizeof(map));
		memset(dis, 0x3f, sizeof(dis));
		for(int i=1; i <= n; i++) map[i][i] = 0;
		while(m--)
		{
			int x, y, w;
			scanf("%d %d %d", &x, &y, &w);
			if(w < map[x][y]) map[x][y] = map[y][x] = w;
		}
		spfa(1);
		printf("%d\n", dis[n]);
	}
	return 0;
} 





HDU - 2544 - 最短路 (最基础单源最短路问题!!dijkstra+floyd+SPFA)