程序员必备十大算法-最短路径（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;
}
 
 
           

运行结果