(16)最短路径.cpp

一些数据结构算法的例子

#include<iostream.h>
#include<conio.h>
#include<stdio.h>
char path[20];
char maxpath[20];
char max;

int NodeCount;
int maxx=200;
char last;
char Node[20];
char Graph[20][20];
void f(int Current,int count,int depth);
char Locate(char Char)
{
	char Temp;
	for(Temp=0;Temp<NodeCount;Temp++)
		if(Node[Temp]==Char)
			break;
	return Temp;
}

void main()
{
	char Temp1,Temp2;
	int Temp3;
	char Condition=1;
	char min,mintemp,mintemp1;
	clrscr();
	for(Temp2=0;Temp2<20;Temp2++)
		for(Temp1=0;Temp1<20;Temp1++)
			Graph[Temp2][Temp1]=0;
	cout<<"Input the node count:";
	cin>>NodeCount;
	cout<<"Input the node:";
	for(Temp1=0;Temp1<NodeCount;Temp1++)
		  cin>>Node[Temp1];
	cout<<"Input the link"<<endl;
	Temp1=0;
	while(1)
	{
		cout<<"Input the first node:";
		cin>>Temp1;
		cout<<"Input the second node:";
		cin>>Temp2;
		cout<<"Input the value:";
		cin>>Temp3;
		if(Temp1=='$')
			break;
		Temp1=Locate(Temp1);
		Temp2=Locate(Temp2);
		Graph[Temp1][Temp2]=Temp3;
	}
	cout<<"Input the last node:";
	cin>>last;
	for(Temp2=0;Temp2<NodeCount;Temp2++)
	{
		for(Temp1=0;Temp1<NodeCount;Temp1++)
			cout<<(int)Graph[Temp2][Temp1]<<" ";
		cout<<endl;
	}
	f(0,0,0);
	for(Temp1=0;Temp1<max;Temp1++)
		cout<<Node[maxpath[Temp1]]<<"->";
	cout<<last<<endl;
	cout<<"Min="<<(int)maxx;
}

void f(int Current,int count,int depth)
{
	int u;
	char s;
	int c;
	if(Node[Current]==last)
	{
		if(count<maxx)
		{
			for(c=0;c<=NodeCount;c++)
				maxpath[c]=path[c];
			max=depth;
			maxx=count;
			return;
		}
	}
	for(u=0;u<NodeCount;u++)
	{
		if(Graph[Current][u]>0)
		{
			s=Graph[Current][u];
			Graph[Current][u]=0;
			path[depth]=Current;
			f(u,count+s,depth+1);
			Graph[Current][u]=s;
		}
	}
}