程式員必備十大算法-最短路徑（2）

最短路徑（2）

時間複雜度為（（m+n）logN）,空間複雜度為M，但是不可以解決負權和帶有負權值的路徑，更不能判斷是否帶有負權或者負權的邊

思路

初始化在第一個站點dis

然後尋找沒有經過的路徑最短的站點（用book數組标記）檢測可以去的路徑是否可以減短

if(dis[k]>dis[u]+a[u][k]) { dis[k]=dis[u]+a[u][k] }

檢測的時候隻用檢查前（n-1）個站點，最後一個站點不用檢測

for(int i=1;i<=n-1;i++)

//最短路徑-Dijkstar(最常用的算法) 
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int a[10][10];
	int m,n,u;
	cin>>n>>m;
	
	for(int i=1;i<=n;i++)
	    for(int j=1;j<=n;j++)
		    if(i==j)a[i][j]=0;
			else a[i][j]=9999;
	
	for(int i=1;i<=m;i++)
	{
		int x,y,t;
		cin>>x>>y>>t;
		a[x][y]=t;
	}
	int *dis=a[1];看不懂的話就用下面的代碼代替
	/*
   for(int i=1;i<=n;i++)
   {
       dis[i]=a[1][i];
   }
   */
	int book[10];
	memset(book,0,sizeof(book));     
	book[1]=1;
	//核心算法
	for(int i=1;i<=n-1;i++)
	{
		int min=9999;
		
		for(int j=1;j<=n;j++)
		{
			if(book[j]==0&&dis[j]<min)
			{
				min=dis[j];
				u=j;
			}
		}
		book[u]=1;
		for(int k=1;k<=n;k++)
		{
			if(a[u][k]<9999)
			{
				if(dis[k]>dis[u]+a[u][k])
				{
					dis[k]=dis[u]+a[u][k];
				}
			}
		}
		
	 } 
	for(int i=1;i<=n;i++)
	    cout<<dis[i]<<" ";
	
	return 0;
}
 
 
           

運作結果