short.cpp

根据题目建立图的结构

// short.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
 #include <stdlib.h>
#include<stdio.h>
 #include <conio.h>

#include <string.h>

#include"iostream.h"
#include"stdlib.h"
#define MAXPOINT  8//定义最大的顶点数目

#define limit  32767   //设置没有路径的权代替无穷大

struct record{          //没个顶点的数据结构设置为一个数组队列
int number;  //顶点号
int flag;    //标志是否从队列中被选过如果为1表示选过为0表示未选
int allpath;  //从源点到这个点的当前最短距离（权最小）
char PathRecord[MAXPOINT+1];//[路径]
}path[MAXPOINT+1]; 
  
char ALLPathRecord[MAXPOINT+1][MAXPOINT+1];//[路径号][路径]

int cost[MAXPOINT+1][MAXPOINT+1];  //用来表示图的邻接矩阵

void main()
{
	int  i,j,temp,front=1,rear=MAXPOINT,N,minnumber,END;
	//temp表示在数组队列中的当前下标 front表示队列首 rear表示队列尾 
	//N 表示待输入的源点号码 minnumber 表示选中的点的号码
	int  min=32768;           //设置一个初始值
	for(i=1;i<=MAXPOINT;i++)
	for(j=1;j<=MAXPOINT;j++)
//	{cout<<"请输入从第"<<i<<"点到第"<<j<<"点的路径长度(权)如果没有路径的话请输入'32767'  "<<endl;
	  cost[i][j]= 32767;        //初始化所有点之间的（权）路径值
//	}
	int q = 1;     //路径数
	cost[1][2] = 1;
	cost[1][3] = 1;
	cost[1][4] = 1;
	cost[2][3] = 1;
	cost[2][7] = 1;
	cost[3][4] = 1;
	cost[3][5] = 1;
	cost[4][6] = 1;
	cost[5][6] = 1;
	cost[5][7] = 1;
	cost[5][8] = 1;
	cost[6][8] = 1;
	cost[7][8] = 1;

	cost[2][1] = 1;
	cost[3][1] = 1;
	cost[4][1] = 1;
	cost[3][2] = 1;
	cost[7][2] = 1;
	cost[4][3] = 1;
	cost[5][3] = 1;
	cost[6][4] = 1;
	cost[6][5] = 1;
	cost[7][5] = 1;
	cost[8][5] = 1;
	cost[8][6] = 1;
	cost[8][7] = 1;

	cout<<"请输入源,终点号"<<endl; //输入一个起点
	scanf("%d,%d",&N,&END);
	//cin>>N;

//	for(N=MAXPOINT;N>=1;N--)//把每一个点轮流地都设置为起点，可以求出任意一对顶点之间的最短路径
	//scanf("%d,%d",&i,&j);
	{ 
		sprintf( path[N].PathRecord, "%d",N);
		for(int i=1;i<=MAXPOINT;i++)
			sprintf( ALLPathRecord[i], "%d",N);//八条路起点
		for(i=front;i<=rear;i++) //初始化每个点的信息
		{if(i==N)
			 path[i].allpath=0;
		  else
		  path[i].allpath=limit;
		  path[i].flag=0;            
		  path[i].number=i;
		}

		while(rear>=1)    //控制循环次数
		{
			
			  for(temp=front;temp<=MAXPOINT;temp++)
			  {   if(path[temp].allpath<min&&path[temp].flag==0)//选出一个具有最值的点
			
      
				  {  
					minnumber=path[temp].number; 
					min=path[temp].allpath ;
				  }
        
			  }
			   min=32768;

			  path[minnumber].flag=1;//把选中的点的标志变量置1表示已经被选过避免选中

			   for(i=1;i<=MAXPOINT;i++)//进行类似广度优先搜索，更新最短路径
			   {
				   if((i!=minnumber)&&(path[minnumber].allpath+cost[minnumber][i]<=path[i].allpath))
				   {
				     path[i].allpath=path[minnumber].allpath+cost[minnumber][i];
				     sprintf(path[i].PathRecord ,"%s%d",  path[minnumber].PathRecord ,i);
					 
						 if(i == END)
						 {
							 q++;
							sprintf(ALLPathRecord[q] ,"%s", path[i].PathRecord);
							
						 }
						 
				   }
				  
			   }

			   rear--;//次数减1
		}
		rear=MAXPOINT; //恢复数组以便于下一点的循环
		//for(j=1;j<=MAXPOINT;j++)
		j=END;
		cout<<"第"<<N<<"点到第"<<j<<"点的最短路径长度（权）为";
		cout<<path[j].allpath <<endl;
		for(int k=3;k<=q;k++)
		{ 
			cout<<"路径"<<ALLPathRecord[k]<<endl;
			//printf(
		}

	}

}