单源最短径dijkstra.cpp

图论的一些常用代码

#include<iostream>
using namespace std;
#define MAXN 500
#define info 1000000
typedef int elemtype;

/*
  功能：单源最短路径（权值类型可改，但必须非负）
  参数：mat 邻接矩阵，n 结点个数，dist 最短路径，path 路径，s 开始位置
  返回：最短路径和
  */
int Dijkstra(int mat[][MAXN],int n,elemtype dist[],int path[],int s)
{
	int i,j,k,mini;
	bool v[MAXN];
		
	for (i=0;i<n;i++)
	{
		dist[i]=mat[s][i];
		v[i]=false;
		//独立的结点，没有任何父结点
		if (dist[i]==info)
			path[i]=-1;
		else 
			path[i]=s;
	}
	v[s]=true;
	for (i=0;i<n-1;i++)
	{
		mini=info;k=0;	//最短路径和顶点
		for (j=0;j<n;j++)
		{
			if (!v[j] && dist[j]<=mini)
			{
				mini=dist[j];
				k =j;		
			}
		}
		v[k]=true;
		for (j=0;j<n;j++)
		{
			if (!v[j] && mat[k][j]+dist[k]<dist[j])
			{
				dist[j] = mat[k][j]+dist[k];
				path[j]=k;
			}
		}
	}
	return 0;
}


/*
 功能：输出树状的路径（用递归）
 参数：path存放着路径，n个数，要到达的结点
 返回：无
 */
void output(int path[],int n,int end)
{
	if (path[end]==-1)
	{
		return;
	}
	else
	{
		end = path[end];
		output(path,n,end);
		cout<<end;
	}

}


int main()
{
	freopen("in.txt","r",stdin);
	int mat[MAXN][MAXN],n;
	cin>>n;
	for (int i=0;i<n;i++)
		for (int j=0;j<n;j++)
			cin>>mat[i][j];
	int dist[MAXN],path[MAXN],s;
	//循环一下变成多源的
	for (int k=0;k<n;k++)
	{
		Dijkstra(mat,n,dist,path,k);
		for (int m=0;m<n;m++)
		{
			if (m==k) continue;
			if (dist[m]==info) 
			{
				cout<<k<<"-->"<<m<<"无法到达"<<endl; continue;
			}
			cout<<k<<"-->"<<m<<"的最短路径为：";
			output(path,n,m);
			cout<<m;
			cout<<"  "<<"长度为："<<dist[m]<<endl;
		}	
		cout<<"----------------------------------------------"<<endl;
	}
	return 0;
}