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

Dijkstra算法求最短路径问题

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

                                   Dijkstra算法求最短路径问题

                                                                                                    ——HM

    图论中最常见的问题就应是最短路径问题了,解决这一问题的几个基本算法有三个:Floyed、Dijkstra和SPFA了。现在我来浅谈一下Dijkstra的思想与实现。

     单纯的Dijkstra并不是很快,算一个点到其余各点的时间复杂度是O(n^2)级别,算每个点到其余各点的复杂度就是O(n^3)了,在提高组竞赛中不占优势,但其进行优化后便很强大了,如用堆优化Dijkstra可以将其复杂度降到O((M+N)logM)了(一说O(MlogM)),可谓强大。

       那现在我们先放下偏见,了解一下最简单的Dijkstra算法。

      这个算法是用了动态规划和贪心的思想,即按照从源点到其余每一顶点的最短路径长度的升序,依次求出从源点到各顶点的最短路径及长度。

       看不懂是吧,我用图来解释。

       假设有一个有向图如下:

      Dijkstra算法求最短路径问题

  1 2 3 4 5
s 1 0 0 0 0
dist 0 3 INF INF 30
path v1 v1,v2     v1,v5

    下面开始进行第一次运算,求出从源点v1到第一个终点的最短路径。首先从s元素为0的对应dist元素中,找出值最小的元素,求得dist[2]的值最小,所以第一个终点为v2,最短路径为path[2]=<v1,v2>,最短距离为dist[2]=3.

    接着把s[2]置为1,表示v2已加入S集合中。然后,以v2为新考虑的中间点,对s元素为0的每个顶点vj(此时3≤j≤5)的目前最短路径长度dist[j]和目前最短路径path[j]进行必要的修改.因dist[2]+GA[2,3]=3+25=28,小于dist[3]=∞,所以将28赋给dist[3],将path[2]并上v3后赋给path[3].

    同理,因dist[2]+GA[2,4]=3+8=11,小于dist[4]= ∞,所以将11赋给dist[4],将path[2]并上v4后赋给path[4],最后再看从v1到v5,以v2作为新考虑的中间点的情况。

    由于v2到v5没有边,故GA[2,5]= ∞,因而dist[2]+GA[2,5]不小于dist[5],因此,dist[5]和path[5]无需修改,应维持原值。

      至此,第一次运算结束,三个一维数组的当前状态为:

  1 2 3 4 5
s 1 1 0 0 0
dist 0 3 15 11 23
path v1 v1,v2 v1,v2,v3 v1,v2,v4 v1,v5

   dist数组就是单点到每个点的最短路径。

最后上代码:

#include <iostream>
#define now dist[m]+ga[m][j]
#define SIZE 10005
using namespace std;

void clear();

int n,e,w,str,maxv=0,m;
int dist[SIZE],ga[SIZE][SIZE],s[SIZE];

int main()
{
	cin>>n>>e;
	for (int i=1;i<=e;i++){
	    int x,y;
	    cin>>x>>y>>w;
	    ga[x][y]=w;
	}
	
	cin>>str;
	
	for (int i=1;i<=n-2;i++){
		w=maxv;
		m=str;
		for (int j=1;j<=n;j++)
			if (s[j]==0 && dist[j]<w){
			    m=j;
			    w=dist[j];
			}
		s[m]=1;
		for (int j=1;j<=n;j++)
		    if (s[j]=0 && now<dist[j])
	                dist[j]=now;
	}
	
	for (int i=1;i<=n;i++)
	    cout<<dist[i]<<' ';
	
	return 0;
}

void clear()
{
	for (int i=1;i<=n;i++){
		if (i!=str) s[i]=0; 
		else	    s[i]=1;
		dist[i]=ga[str][i];
	}
}

    谢谢观看。