[e-mail]

最短路径问题 迪克斯特拉算法和弗洛伊德算法

#include <iostream>
using namespace std;

#define MAXV 50
#define INF 10000

typedef int InfoType;

//邻接矩阵存储方法
/*typedef struct
{
    int no;
    InfoType info;
} VertexType;
*/
typedef struct
{
	int edges[MAXV][MAXV];
    int n;
    //VertexType vexs[MAXV];
} MGraph;

//狄克斯特拉算法
void Ppath(int path[],int i,int v)//递归输出经过的中间节点
{
    int k;
    k=path[i];
    if(k==v) return;
    Ppath(path,k,v);
    cout<<k;
}


void Dispath(int dist[],int path[],int s[],int n,int v)
{
    int i;
    for(i=0;i<n;i++)
	{
        if(i==v) continue;
        if(s[i]==1)
		{
			cout<<"从DS"<<"到S"<<i<<"的最短路径为："<<dist[i]<<" ";
            cout<<v;        //输出起点
            Ppath(path,i,v);//输出经过的中间节点
            cout<<i<<endl;  //输出终点
		}
		else
			cout<<"从DS"<<"到S"<<i<<"不存在的路径"<<endl;
	}
}

//狄克斯特拉算法
void Dijkstra(MGraph g,int v)
{   //dist[]存储节点s[]的最短路径；
	//path[]存储路径终点的上一个节点；
	int dist[MAXV],path[MAXV];
	int s[MAXV];
    int mindis,i,j,u;
    for(i=0;i<g.n;i++)
	{
		dist[i]=g.edges[v][i];
        s[i]=0;
        if(g.edges[v][i]<INF) path[i]=v;
		else path[i]=-1;
	}
	s[v]=1;path[v]=0;
	for(i=0;i<g.n;i++)
	{
		mindis=INF;
		for(j=0;j<g.n;j++)//判断可以通过那些其他中间节点s[u]进行松弛
		{
			if(s[j]==0&&dist[j]<mindis)
			{
				u=j;
				mindis=dist[j];
			}
		}
		s[u]=1;//DS通过节点s[u]进行松弛
		for(j=0;j<g.n;j++)
		{
			if(s[j]==0)
			{
				if(g.edges[u][j]<INF&&dist[u]+g.edges[u][j]<dist[j])
				{
					dist[j]=dist[u]+g.edges[u][j];
					path[j]=u; //把经过的中间节点存入path[]
				}
			}
		}
	}
	Dispath(dist,path,s,g.n,v);
}

//弗洛伊德算法
void Ppath1(int path[][MAXV],int i,int j)
{
	int k;
	k=path[i][j];
	if(k==-1) return;
	cout<<k;
	Ppath1(path,k,j);
}

void Dispath1(int A[][MAXV],int path[][MAXV],int n)
{
	int i,j;
	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
		{
			if(i==j) continue;
			if(A[i][j]==INF)//无穷大
			{
				if(i!=j)
					cout<<"从"<<i<<"到"<<j<<"不存在路径"<<endl;
			}
			else
			{
				cout<<"从"<<i<<"到"<<j<<"的最短路径长度为:"<<A[i][j]<<" ";
				cout<<i;
				Ppath1(path,i,j);
				cout<<j<<endl;
			}
		}
	}
	//输出变换后的矩阵
	cout<<"变换后的A[i][j]矩阵为："<<endl;
	for(i=0;i<n;i++)
		{
			for(j=0;j<n;j++)
			{
				cout<<A[i][j];
			}
		}
	cout<<endl;
	for(i=0;i<n;i++)
		{
			for(j=0;j<n;j++)
			{
				cout<<path[i][j];
			}
		}
}

//弗洛伊德算法
void Floyd(MGraph g)
{
	int A[MAXV][MAXV],path[MAXV][MAXV];
	int i,j,k;
	for(i=0;i<g.n;i++)
	{
		for(j=0;j<g.n;j++)
		{
			A[i][j]=g.edges[i][j];
			path[i][j]=-1;
		}
	}
	for(k=0;k<g.n;k++)//K为经过的中间节点
	{
		for(i=0;i<g.n;i++)//i为源点
		{
			for(j=0;j<g.n;j++)//j为终点
			{
				if(A[i][j]>A[i][k]+A[k][j])
				{
					A[i][j]=A[i][k]+A[k][j];
					path[i][j]=k;
				}
			}
		}
	}
	Dispath1(A,path,g.n);
}

//主函数
int main()
{
	int i,j,n;
	MGraph g;
	cout<<"请输入带权图的顶点个数：";//例如输入4
	while(scanf("%d",&n)!=EOF/*cin>>n,n!=EOF*/)
	{
		cout<<"请输入带权图的邻接矩阵："<<endl;
/*输入格式如下
0 1 3 7
6 0 4 3
1 4 0 2
5 7 1 0
*/

		for(i=0;i<n;i++)
		{
			for(j=0;j<n;j++)
			{
                //scanf("%d",&g.edges[i][j]);
				cin>>g.edges[i][j];
			}
		}
		g.n=n;
		cout<<"采用迪杰斯特拉算法得到的最短路径为："<<endl;
        
		Dijkstra(g,0);
        
		Dijkstra(g,3);
		
		cout<<endl;

		cout<<"采用弗洛伊德算法得到的最短路径为："<<endl;
		Floyd(g);
		
		cout<<endl;
		break;
	}
	return 0;
}