//具體題目為計算機算法基礎課本125頁的圖
//先利用最優性原理找出所有節點最短路徑長度
//再利用所有節點的最短路徑長度通過回溯的方法找到所有最短的路徑
#include
using?namespace?std;
#define	E	1000
#define	MAX	1000
bool	cal_path（int	data[][12]int	less[]int?now_nodeint	path[3]int?level）;

int?main（）
{
	int	data[12][12]={//?1??2??3??4??5??6??7??8??9??10?11?12
						{0?9?7?3?2?E?E?E?E?E?E?E}
						{E?0?E?E?E?4?2?1?E?E?E?E}
						{E?E?0?E?E?2?7?E?E?E?E?E}
						{E?E?E?0?E?E?E?11E?E?E?E}
						{E?E?E?E?0?E?118?E?E?E?E}
						{E?E?E?E?E?0?E?E?6?5?E?E}
						{E?E?E?E?E?E?0?E?4?3?E?E}
						{E?E?E?E?E?E?E?0?E?5?6?E}
						{E?E?E?E?E?E?E?E?0?E?E?4}
						{E?E?E?E?E?E?E?E?E?0?E?2}
						{E?E?E?E?E?E?E?E?E?E?0?5}
						{E?E?E?E?E?E?E?E?E?E?E?0}
				?};	
	int	less[12]={000000000000};	//less代表對應節點至終點（也就是11這個點）的最短路徑長度
	
	int	next_node;
	int	min;

	//	計算每個節點到終端節點最短路徑的長度
	for（int?now_node=10;now_node>=0;now_node--）	//從10開始算，不從11開始。
	{
		min=MAX;			//最大值
		for（next_node=now_node+1;next_node<=11;next_node++）
		{
			if（data[now_node][next_node]==E）
			{
				continue;		//兩個節點間無連接
			}

			if（data[now_node][next_node]+less[next_node]			{
				min=data[now_node][next_node]+less[next_node];
			}
		}
		less[now_node]=min;
	}

	cout<<“最短路徑長度為:?“<	
	int	path[3]={-1-1-1};
	cal_path（dataless0path0）;
	return?0;
}

bool	cal_path（int	data[][12]int	less[]int?now_nodeint	path[3]int?level）
//利用回溯找出所有最短的路徑
//必須以now_node=0level=0path[]={-1-1-1}開始調用（-1代表的是沒找到路徑節點，便于調試）
{
	int	next_node;
	if（now_node==11）	//找到了終點，打印路徑結果
	{
		cout<<“1?->?“;
		for（int?i=0;i<3;i++）
		{
			cout<?“;
		}
		cout<<12<		return?true;
	}

	for（next_node=now_node+1;next_node<=11;next_node++）
	{
		if（data[now_node][next_node]?==?E）	//兩節點間無連接，跳過
		{
			continue;
		}
		if（?data[now_node][next_node]+less[next_node]==less[now_node]?）
		{
			path[level]=next_node;
			cal_path（datalessnext_nodepathlevel+1）;
		}
	}
	path[level]=-1;				//回溯時要恢復path[]中的值
	return?false;
}

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----

?????文件???????2376??2008-11-21?13:42??多段圖最短路徑\多段圖.cpp

?????文件???????3403??2008-11-19?21:46??多段圖最短路徑\多段圖.dsp

?????文件????????520??2008-11-19?23:02??多段圖最短路徑\多段圖.dsw

?????文件??????41984??2008-11-21?13:38??多段圖最短路徑\多段圖.ncb

?????文件??????48640??2008-11-21?13:38??多段圖最短路徑\多段圖.opt

?????文件???????1163??2008-11-21?13:38??多段圖最短路徑\多段圖.plg

?????文件?????110592??2008-11-21?13:38??多段圖最短路徑\Debug\vc60.pdb

?????文件?????150804??2008-11-21?13:38??多段圖最短路徑\Debug\多段圖.obj

?????文件????1082368??2008-11-21?13:38??多段圖最短路徑\Debug\多段圖.pdb

?????目錄??????????0??2010-02-15?13:45??多段圖最短路徑\Debug

?????目錄??????????0??2010-02-15?13:45??多段圖最短路徑

-----------?---------??----------?-----??----

??????????????1441850????????????????????11