多段图最短路径算法课实验

多段图最短路径，算法课的一个小实验 先利用最优性原理找出所有节点最短路径长度 再利用所有节点的最短路径长度通过回溯的方法找到所有最短的路径

//具体题目为计算机算法基础课本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