//具體題目為計(jì)算機(jī)算法基礎(chǔ)課本125頁(yè)的圖
//先利用最優(yōu)性原理找出所有節(jié)點(diǎn)最短路徑長(zhǎng)度
//再利用所有節(jié)點(diǎn)的最短路徑長(zhǎng)度通過(guò)回溯的方法找到所有最短的路徑
#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代表對(duì)應(yīng)節(jié)點(diǎn)至終點(diǎn)（也就是11這個(gè)點(diǎn)）的最短路徑長(zhǎng)度
	
	int	next_node;
	int	min;

	//	計(jì)算每個(gè)節(jié)點(diǎn)到終端節(jié)點(diǎn)最短路徑的長(zhǎng)度
	for（int?now_node=10;now_node>=0;now_node--）	//從10開(kāi)始算，不從11開(kāi)始。
	{
		min=MAX;			//最大值
		for（next_node=now_node+1;next_node<=11;next_node++）
		{
			if（data[now_node][next_node]==E）
			{
				continue;		//兩個(gè)節(jié)點(diǎn)間無(wú)連接
			}

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

	cout<<“最短路徑長(zhǎng)度為:?“<	
	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}開(kāi)始調(diào)用（-1代表的是沒(méi)找到路徑節(jié)點(diǎn)，便于調(diào)試）
{
	int	next_node;
	if（now_node==11）	//找到了終點(diǎn)，打印路徑結(jié)果
	{
		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）	//兩節(jié)點(diǎn)間無(wú)連接，跳過(guò)
		{
			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;				//回溯時(shí)要恢復(fù)path[]中的值
	return?false;
}

?屬性????????????大小?????日期????時(shí)間???名稱
-----------?---------??----------?-----??----

?????文件???????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