dijskstra_algorithm.cpp

求有向网最短路径

// Dijskstra_algorithm.cpp : Defines the entry point for the console application.
//利用Dijkstra算法求有向网的每对顶点之间的最短路径,该算法的时间复杂度为O(2*n^3);
//利用Floyd算法求有向网的每对顶点之间的最短路径,该算法的时间复杂度为O(n^3);

/*------------------	
【作者】:洪蕾
【日期】：2004-12-12
【版本号】：1.0
 ------------------*/

#include "stdafx.h"
#include "stdio.h"
#include "malloc.h"
#define MaxCost 9999

/*--------------------------------------
【结构体说明】:定义n*m的矩阵
--------------------------------------*/
typedef struct MatrixRow
{
	int *jCol;
}MatrixRow;
typedef struct Matrix
{
	 MatrixRow *iRow;
}Matrix;

/*------------------------------------
【函数名称】:DefMatrix
【功    能】:给一个n*m阶矩阵分配内存
【输    入】:矩阵的阶数n和m
【返    回】:分好内存的矩阵A
--------------------------------------*/
Matrix *DefMatrix(Matrix *A,int n,int m)
{
	int i,j;

	A = (Matrix*)malloc(sizeof(Matrix));
	A->iRow = (MatrixRow*)malloc(sizeof(MatrixRow)*n);
	for(i=0;i<n;i++)
		for(j=0;j<m;j++)
			A->iRow[i].jCol = (int*)malloc(sizeof(int)*m);

	return (A);
}

/*--------------------------------------
【函数名称】:InputCost
【功    能】:输入有向网的邻接矩阵
【输    入】:任意两顶点的序号及权值
【返    回】:邻接矩阵
--------------------------------------*/
void InputCost(int n,Matrix *Cost)
{
	int i,j;
	int V1,V2,w;

	//Cost = DefMatrix(Cost,n,n);	

	//初始化邻接矩阵：
	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
			Cost->iRow[i].jCol[j] = MaxCost;		
		Cost->iRow[i].jCol[i] = 0;
	}

	printf("请输入顶点V1和V2的序号及其权值:\n");
	scanf("%d %d %d",&V1,&V2,&w);

	while(V1 != -1 && V2 != -1)
	{
		Cost->iRow[V1-1].jCol[V2-1] = w;
		scanf("%d %d %d",&V1,&V2,&w);//
	}
}

/*-----------------------------------------------------------
【函数名称】:Dijkstra
【功    能】:用Dijkstra算法求有向网中任意两顶点之间的最短距离
【输    入】:邻接矩阵Cost及其阶数n
【返    回】:存储任意两顶点之间的最短距离的矩阵Distance
-------------------------------------------------------------*/
void Dijkstra(Matrix *Cost,int n,Matrix *Distance)
{
	int i,j,misDis,u,t;
	int *s;	
	
	//分配内存:
	s = (int*)malloc(sizeof(int)*n);
	
	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
		{
			Distance->iRow[i].jCol[j] = Cost->iRow[i].jCol[j];
			s[j] = 0;
		} 
		s[i] = 1; //记录源点
		
		for(t=1;t<n;t++)
		{
			misDis = MaxCost;
			for(j=0;j<n;j++)
			{
				if((s[j] == 0)&&(Distance->iRow[i].jCol[j] < misDis))
				{
					u = j;
					misDis = Distance->iRow[i].jCol[j];
				}
			}
			s[u] = 1;

			for(j=0;j<n;j++)
			{
				if(s[j] == 0)
				{
					misDis = (Distance->iRow[i].jCol[u]) + (Cost->iRow[u].jCol[j]);			
					Distance->iRow[i].jCol[j] = (Distance->iRow[i].jCol[j] < misDis) ? Distance->iRow[i].jCol[j] : misDis;
				}
			}
		}
	}

	printf("\n----用Dijkstra算法求有向网中任意两顶点之间的最短距离-----\n");
	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
			printf("%4d    ",Distance->iRow[i].jCol[j]);
		printf("\n");
	}
}

/*--------------------------------------------------------
【函数名称】:Floyd
【功    能】:用Floyd算法求有向网中任意两顶点之间的最短距离
【输    入】:邻接矩阵Cost及其阶数n
【返    回】:存储任意两顶点之间的最短距离的矩阵Weight
----------------------------------------------------------*/
void Floyd(Matrix *Cost,int n,Matrix *Weight)
{
	int i,j,k;
	Matrix *Path;

	Path = DefMatrix(Path,n,n);

	//初始化
	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
		{
			Weight->iRow[i].jCol[j] = Cost->iRow[i].jCol[j];
			Path->iRow[i].jCol[j] = 0;
		}

	for(k=0;k<n;k++)
		for(i=0;i<n;i++)
			for(j=0;j<n;j++)
			{
				if(Weight->iRow[i].jCol[j] > Weight->iRow[i].jCol[k] + Weight->iRow[k].jCol[j] )
					Weight->iRow[i].jCol[j] = Weight->iRow[i].jCol[k] + Weight->iRow[k].jCol[j];
				Path->iRow[i].jCol[j] = k;
			}

	printf("\n------用Floyd算法求有向网中任意两顶点之间的最短距离-------\n");
	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
			printf("%4d    ",Weight->iRow[i].jCol[j]);
		printf("\n");
	}
}




void main(int argc, char* argv[])
{ 
	int n;
	Matrix *Cost,*Distance,*Weight;	
	
	printf("\n请输入顶点个数：\n");
	scanf("%d",&n);
	
	//分配内存
	Cost = DefMatrix(Cost,n,n);
	//输入邻接矩阵
	InputCost(n,Cost);	

	//分配内存
	Distance = DefMatrix(Distance,n,n);	
	//用Dijkstra算法求有向网中任意两顶点之间的最短距离
	Dijkstra(Cost,n,Distance);

	//分配内存
	Weight = DefMatrix(Weight,n,n);	
	//用Floyd算法求有向网中任意两顶点之间的最短距离
	Floyd(Cost,n,Weight);
		
	getchar();
	getchar();

}