最短路徑問題-Dijstra

最短路徑問題

問題來源：hdu-3790

Problem Description

給你n個點，m條無向邊，每條邊都有長度d和花費p，給你起點s終點t，要求輸出起點到終點的最短距離及其花費，如果最短距離有多條路線，則輸出花費最少的。

Input

輸入n,m，點的編号是1~n,然後是m行，每行4個數 a,b,d,p，表示a和b之間有一條邊，且其長度為d，花費為p。最後一行是兩個數 s,t;起點s，終點。n和m為0時輸入結束。

(1<n<=1000, 0<m<100000, s != t)

Output

輸出 一行有兩個數， 最短距離及其花費。

Sample Input

3 2

1 2 5 6

2 3 4 5

1 3

0 0

Sample Output

9 11

源代碼:

#include<stdio.h>
#include<string.h>
#define MAX 1006
#define INF 999999999

int map[MAX][MAX] , cost[MAX][MAX] , mark[MAX] , dis[MAX] , value[MAX];
//map[i][j]存儲雙向地圖,存儲i點到j點的距離
//cost[i][j]存儲i點到j點的花費
//mark[i]标志i點手否被更新過
//dis[i]是i點到源點s的最短距離
//value[i]是i點到源點s的最短花費

void Dijstra( int map[][MAX] , int N , int s , int t );

int main( ){
	int N , M;
	int a , b , c , d , s , t;

	while( ~scanf("%d%d",&N,&M) && N+M!=0 ){
		for( int i=1 ; i<=N ; i++ )
			for( int j=1 ; j<=N ; j++ ){
				map[i][j] = cost[i][j] = INF;	//輸入前初始化
				map[i][i] = cost[i][i] = 0;
			}

		for( int i=1 ; i<=M ; i++ ){
			scanf("%d%d%d%d",&a,&b,&c,&d);
			if( c < map[a][b] ){		//重邊長度不等的情況
				map[a][b] = map[b][a] = c;
				cost[a][b] = cost[b][a] = d;
			}	//重邊相等長度的情況
			else if( c==map[a][b] && d<cost[a][b] ){
				cost[a][b] = cost[b][a] = d;
			}
		}

		scanf("%d%d",&s,&t);

		Dijstra(map,N,s,t);
	}

	return 0;
}


void Dijstra( int map[][MAX] , int N , int s , int t ){
//算法思路:最短路徑遞增,隻适用于非負權邊
	int min , k , last=s;

	memset( mark , 0 , sizeof( mark ) );

	for( int i=1 ; i<=N ; i++ ){
		dis[i] = map[s][i];
		value[i] = cost[s][i];
	}

	mark[s] = 1;	//源點标記

	while( 1 ){
		for( int i=1 , min=INF ; i<=N ; i++ ){	//尋找下一個dis最短的點
			if( mark[i]==0 && dis[i]<min ){
				min = dis[k=i];
			}
		}

		mark[k] = 1;	//标記dis最短的邊

		if( k==t ){
			printf("%d %d\n",dis[t],value[t]);
			return ;
		}

		for( int j=1 , min=INF ; j<=N ; j++ ){	//k點來松弛其他節點長度和花費
				if( dis[k] + map[k][j] < dis[j] ){
					dis[j] = dis[k] + map[k][j];
					value[j] = value[k] + cost[k][j];
				}
				else if( dis[k]+map[k][j]==dis[j]  && value[k]+cost[k][j]<value[j] ){
					value[j] = value[k] + cost[k][j];
				}
		}
	}
}
           

代碼分析:采用了Dijstra算法(求單源點到其他點的最短路徑),時間複雜度為O(n^2),分為三個步驟:尋找、标記、松弛。

Prim算法與Dijstra算法的差別：Prim是計算最小生成樹的算法、Dijkstra是計算最短路徑的算法；Prim算法的更新操作更新的cls是已通路集合到未通路集合中各點的距離；Dijkstra算法的更新操作更新的cls是源點到未通路集合中各點的距離，已經通路過的相當于已經找到源點到它的最短距離了；