//?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*

//圖的鄰接矩陣數(shù)據(jù)結(jié)構(gòu)
typedef?struct?tag_ALGraph
{
	float?**arcs;//鄰接矩陣
	int?VexNumArcNum;//頂點和弧的數(shù)目
}ALGraph;


/////////////////////////////
//函數(shù)聲明部分
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）;
//函數(shù)的調(diào)用以及數(shù)據(jù)變量的定義和使用，注意要建立在前面已經(jīng)聲明實現(xiàn)以及定義了的基礎(chǔ)上


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+“）;
	//由于頂點數(shù)目過多，直接分配靜態(tài)棧大小將超過2G，故此處采用動態(tài)分配內(nèi)存
	//此處動態(tài)分配二維數(shù)組
????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）
	{
		//開辟內(nèi)存
		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?		{
			for?（??j?=?0;?j?			{
				arrPath[i][j]?=?i;
			}
		}
		
		//?先初始化arrDis
		for?（?i?=?0;?i?		{		
			for?（?j?=?0;?j?			{			
				arrDis[i][j]?=?G.arcs[i][j];
				if?（i==j）?arrDis[i][j]=0;
			}		
		}
		floyd（arrDisarrPathG.VexNum）;
	//	Show_Floyd（arrDisarrPathG.VexNum）;
	//銷毀內(nèi)存，程序注意釋放內(nèi)存以避免內(nèi)存不足
?	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