Dijskra算法 floyd算法

使用c语言，基于win32的工程，实现从文件读取弧段到图，然后实现Dijskra算法和floyd算法，并将结果写入txt文件

// ShortPath.cpp : Defines the entry point for the console application.
#include “stdlib.h“
#include “stdio.h“
#include “iostream.h“
#include “Stack.h“
#include “omp.h“
#define min（ab） a#define  MAX_VERTEX_COUNT 13000
#define INFINITY 100000000.0
#define PathMatrix int*
#define ShortPathTable float*

//图的邻接矩阵数据结构
typedef struct tag_ALGraph
{
	float **arcs;//邻接矩阵
	int VexNumArcNum;//顶点和弧的数目
}ALGraph;


/////////////////////////////
//函数声明部分
void ShortestPath_DIJ（ALGraph Gint v0PathMatrix PShortPathTable D）;
void ShortestPath_Floyd（ALGraph Gfloat **DisMatrix）;
void floyd（ float **_arrDis int **_arrPath int _nVertexCount ）;
void Show_Floyd（ float **_arrDis int **_arrPath int _nVertexCount ）;
void Show_DIJ（PathMatrix PShortPathTable Dint _nVertexCountint v0）;
//函数的调用以及数据变量的定义和使用，注意要建立在前面已经声明实现以及定义了的基础上


int main（int argc char* argv[]）
{
	ALGraph G;
	int i = 0j=0;
	int h=0t=0;
	float w = 0.0;
    FILE *fp=fopen（“Floyd_Graph.dat““r+“）;
//s	 FILE *fp=fopen（“444.dat““r+“）;
	//由于顶点数目过多，直接分配静态栈大小将超过2G，故此处采用动态分配内存
	//此处动态分配二维数组
    G.arcs=（float **）malloc（sizeof（float **）*MAX_VERTEX_COUNT）;
	for （i=0;i	{
		G.arcs[i]=（float *）malloc（sizeof（float *）*MAX_VERTEX_COUNT）;
	}
	
	//矩阵初始化
	for （i=0;i	{
		for （j=0;j		{
			G.arcs[i][j]=INFINITY;
		}
	}
	G.ArcNum=0;G.VexNum=0;
	//读取弧段和顶点
    char ch;
	while（ch!=EOF）
	{
		fscanf（fp“%d“&h）;//弧头
		fscanf（fp“%d“&t）;//弧尾
        if （h>G.VexNum）
        {
			G.VexNum=h;
        }
		if （t>G.VexNum）
		{
			G.VexNum=t;
		}
		fscanf（fp“%f“&w）;
		G.arcs[h][t]=w;
		G.ArcNum++;
		ch=fgetc（fp）;   
	}
	fclose（fp）;

	printf（“请选择最短路径算法，0 for Dijistk算法，1 for Floyd算法“）;
	int a;
	scanf（“%d“&a）;
	if （a==0）
	{
		//开辟内存
		PathMatrix P = new int[G.VexNum+1];
		ShortPathTable D = new float[G.VexNum+1];
		int v0=0;
		ShortestPath_DIJ（Gv0PD）;//计算最短路径
		Show_DIJ（PDG.VexNumv0）;	
		delete []P;P=NULL;
     	delete []D;D=NULL;
		delete []G.arcs;G.arcs=NULL;
	}
	else if （a==1）
	{
		int **arrPath=（int**）malloc（（G.VexNum+1）*sizeof（int**））;
		for （i=0;i		{
			arrPath[i]=（int*）malloc（（G.VexNum+1）*sizeof（int*））;
		}  
		float **arrDis=（float**）malloc（（G.VexNum+1）*sizeof（float**））;
		for （i=0;i		{
			arrDis[i]=（float*）malloc（（G.VexNum+1）*sizeof（float*））;
		}
		
		// 先初始化_arrPath
		for （  i = 0; i < G.VexNum+1; ++i ）
		{
			for （  j = 0; j < G.VexNum+1; ++j ）
			{
				arrPath[i][j] = i;
			}
		}
		
		// 先初始化arrDis
		for （ i = 0; i < G.VexNum+1; ++i ）	
		{		
			for （ j = 0; j < G.VexNum+1; ++j ）			
			{			
				arrDis[i][j] = G.arcs[i][j];
				if （i==j） arrDis[i][j]=0;
			}		
		}
		floyd（arrDisarrPathG.VexNum）;
	//	Show_Floyd（arrDisarrPathG.VexNum）;
	//销毁内存，程序注意释放内存以避免内存不足
 	delete []arrPath;arrPath=NULL;
 	delete []arrDis;arrDis=NULL;
	delete []G.arcs;G.arcs=NULL;
	}
	return 0;
}

void 

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     文件        4497  2013-04-14 16:42  NetWork Analysis.dsp
     文件         540  2013-04-07 15:33  NetWork Analysis.dsw
     文件       50176  2013-04-14 22:28  NetWork Analysis.ncb
     文件       54784  2013-04-14 22:28  NetWork Analysis.opt
     文件        1864  2013-04-14 22:23  NetWork Analysis.plg
     文件       10077  2013-04-14 22:23  ShortPath.cpp
     文件        2504  2013-04-13 19:56  Stack.h
     文件      261332  2013-04-14 16:55  result_DIJ.txt
     文件    12323741  2013-04-14 17:51  result_Floyd.txt