📄 mainuse.cpp
字号:
#include "Dijkstra.h"
#include "dataRead.h"
#define min(C,D) C<D ? C:D
#define max(C,D) C>D ? C:D
#define NON_DIRCTION_LINK 250000
#define N 3957
#define ALLESTATION 50000
#define ALLSTATION 5000
#define MAXPRICE 1000
typedef struct StationInfo
{
int busNumber; //公交路数
int directType; //方向 上行 下行 环形 1 2 3 4
int priceType; //收费方式 10 11 13
int stationNum; //本公交路数的总的站点数
int itvStation; //用于后面回溯站点 站点间隔
}StationInfo;
typedef struct TansInfo
{
int timeCost; //时间花费
int preStation; //前一站
int step; //阶数
int busNumber; //公交路数
int directType; //方向 上行 下行 环形 1 2 3 4
int priceType; //收费方式 10 11 13
}TansInfo;
int AllEStation[ALLESTATION];
void* AllStation[ALLSTATION];
int A[N][N];
int P[N][N];
StationInfo S[N][N];
TansInfo TT[N][N];
int Trans[N][N];
int TransTime[N][N];
void Init();
void GetA();
void GetP(); //获取P矩阵
void GetTansTime();
void GetTans();
void GetTT();
int main(void)
{
int sourceNode,destinationNode;
printf("请输入源结点号(<6):\n");
scanf("%d",&sourceNode);
printf("请输入目的结点号(<6):\n");
scanf("%d",&destinationNode);
if(sourceNode<0 || destinationNode<0 ||sourceNode>N || destinationNode>N)
{ printf("输入错误！\n");
return 1;
}
sourceNode--;
destinationNode--;
FILE *fp;
if((fp=fopen("bus.txt","r+")) != NULL)
{
printf("文件打开正常\n");
}
//memset(AllStation,0,sizeof(int)*ALLSTATION);
ReadFile(AllStation,fp);
Init(); //初始化A
GetA(); //获取A矩阵
GetP(); //获取P矩阵
GetTT();
GetTansTime();
GetTans();
//基于最短时间***************************************************************
Node B[N];
int newGrowNode;
for (int i=0;i<N;i++)
{
B[i].node=i;
B[i].flag=0;
B[i].path.node = -1;
B[i].path.nextNode=NULL;
B[i].distance=NON_DIRCTION_LINK;
}
for (i=0;i<N;i++)
{
if (A[sourceNode][i] != NON_DIRCTION_LINK)
{
B[i].distance=A[sourceNode][i]; //与源节点的直达距离
B[i].path.node=sourceNode;
}
} //加入节点只有源节点
B[sourceNode].flag = 1; //初始化节点
B[sourceNode].path.node = -1;
while(B[destinationNode].flag != 1)
{
newGrowNode=Get_Next_Grow_Node(B,N);
B[newGrowNode].flag=1;
for (int i=0;i<N;i++)
{
if (B[i].flag==0 && (B[i].distance > B[newGrowNode].distance+A[newGrowNode][i]) )
{
B[i].path.node=newGrowNode; //把新加入的节点加入到路径 修改路径链表
B[i].distance=B[newGrowNode].distance+A[newGrowNode][i];//修改临时路径值
}
}
}
//输出路径以及长度
if (B[destinationNode].distance == NON_DIRCTION_LINK)
{
printf("路径不可达!\n");
}
else
{
int crtStation = destinationNode;
int preStation = B[destinationNode].path.node;
int allCost=0;
printf("\n\n/******基于最短时间******/\n");
printf("最短路径为:\n");
while(preStation != -1)
{
printf("%4d -> %4d : ",preStation+1,crtStation+1);
printf("%4d,%4d,%4d,%4d\n",S[preStation][crtStation].busNumber,S[preStation][crtStation].directType,S[preStation][crtStation].priceType,S[preStation][crtStation].itvStation);
allCost+=P[preStation][crtStation];
crtStation = preStation;
preStation = B[preStation].path.node;
}
printf("最短时间为:%3d\n",B[destinationNode].distance-5);
printf("对应花费为:%3d\n",allCost);
}
//基于最短时间结束********************************************************************
//基于最小耗费***************************************************************************
for (i=0;i<N;i++)
{
B[i].node=i;
B[i].flag=0;
B[i].path.node = -1;
B[i].path.nextNode=NULL;
B[i].distance=MAXPRICE;
}
for (i=0;i<N;i++)
{
if (P[sourceNode][i] != MAXPRICE)
{
B[i].distance=P[sourceNode][i]; //与源节点的直达距离
B[i].path.node=sourceNode;
}
} //加入节点只有源节点
B[sourceNode].flag = 1; //初始化节点
B[sourceNode].path.node = -1;
while(B[destinationNode].flag != 1)
{
newGrowNode=Get_Next_Grow_Node(B,N);
B[newGrowNode].flag=1;
for (int i=0;i<N;i++)
{
if (B[i].flag == 0 && (B[i].distance > B[newGrowNode].distance+P[newGrowNode][i]) )
{
B[i].path.node=newGrowNode; //把新加入的节点加入到路径 修改路径链表
B[i].distance=B[newGrowNode].distance+P[newGrowNode][i];//修改临时路径值
}
}
}
//输出路径以及长度
if (B[destinationNode].distance == MAXPRICE)
{
printf("不可达!\n 再多钱也没用");
}
else
{
int crtStation = destinationNode;
int preStation = B[destinationNode].path.node;
int timeCost=0;
printf("\n\n/******基于小花费******/\n");
printf("最小耗费路径为:\n");
while(preStation != -1)
{
printf("%4d -> %4d : ",preStation+1,crtStation+1);
printf("%4d,%4d,%4d,%4d,花费:%4d\n",S[preStation][crtStation].busNumber,S[preStation][crtStation].directType,S[preStation][crtStation].priceType,S[preStation][crtStation].itvStation,P[preStation][crtStation]);
timeCost+=A[preStation][crtStation];
crtStation = preStation;
preStation = B[preStation].path.node;
}
printf("最小耗费为:%3d\n",B[destinationNode].distance);
printf("对应时间花费为:%3d\n",timeCost-5);
}
//基于最小耗费结束************************************************************************
//基于最少转乘次数***************************************************************
for (i=0;i<N;i++)
{
B[i].node=i;
B[i].flag=0;
B[i].path.node = -1;
B[i].path.nextNode=NULL;
B[i].distance=NON_DIRCTION_LINK;
}
for (i=0;i<N;i++)
{
if (Trans[sourceNode][i] != NON_DIRCTION_LINK)
{
B[i].distance=Trans[sourceNode][i]; //与源节点的直达距离
B[i].path.node=sourceNode;
}
} //加入节点只有源节点
B[sourceNode].flag = 1; //初始化节点
B[sourceNode].path.node = -1;
while(B[destinationNode].flag != 1)
{
newGrowNode=Get_Next_Grow_Node(B,N);
B[newGrowNode].flag=1;
for (int i=0;i<N;i++)
{
if (B[i].flag==0 && (B[i].distance > B[newGrowNode].distance+Trans[newGrowNode][i]) )
{
B[i].path.node=newGrowNode; //把新加入的节点加入到路径 修改路径链表
B[i].distance=B[newGrowNode].distance+Trans[newGrowNode][i];//修改临时路径值
}
}
}
//输出路径以及长度
if (B[destinationNode].distance == NON_DIRCTION_LINK)
{
printf("路径不可达!\n");
}
else
{
int crtStation = destinationNode;
int preStation = B[destinationNode].path.node;
int allCost=0;
int timeCost=0;
printf("\n\n/******基于最少转乘次数******/\n");
printf("最短路径为:\n");
while(preStation != -1)
{
printf("%4d -> %4d : ",preStation+1,crtStation+1);
printf("%4d,%4d,%4d,%4d\n",S[preStation][crtStation].busNumber,S[preStation][crtStation].directType,S[preStation][crtStation].priceType,S[preStation][crtStation].itvStation);
allCost += P[preStation][crtStation];
timeCost+= A[preStation][crtStation];
crtStation = preStation;
preStation = B[preStation].path.node;
}
printf("最少转乘次数为:%3d\n",B[destinationNode].distance);
printf("对应花费为:%3d\n",allCost);
printf("对应时间为:%3d\n",timeCost);
}
//基于最少转乘次数结束********************************************************************
//基于最少转乘次优先随后最短时间***************************************************************
for (i=0;i<N;i++)
{
B[i].node=i;
B[i].flag=0;
B[i].path.node = -1;
B[i].path.nextNode=NULL;
B[i].distance=NON_DIRCTION_LINK;
}
for (i=0;i<N;i++)
{
if (TransTime[sourceNode][i] != NON_DIRCTION_LINK)
{
B[i].distance=TransTime[sourceNode][i]; //与源节点的直达距离
B[i].path.node=sourceNode;
}
} //加入节点只有源节点
B[sourceNode].flag = 1; //初始化节点
B[sourceNode].path.node = -1;
while(B[destinationNode].flag != 1)
{
newGrowNode=Get_Next_Grow_Node(B,N);
B[newGrowNode].flag=1;
for (int i=0;i<N;i++)
{
if (B[i].flag==0 && (B[i].distance > B[newGrowNode].distance+TransTime[newGrowNode][i]) )
{
B[i].path.node=newGrowNode; //把新加入的节点加入到路径 修改路径链表
B[i].distance=B[newGrowNode].distance+TransTime[newGrowNode][i];//修改临时路径值
}
}
}
//输出路径以及长度
if (B[destinationNode].distance == NON_DIRCTION_LINK)
{
printf("路径不可达!\n");
}
else
{
int crtStation = destinationNode;
int preStation = B[destinationNode].path.node;
int allCost = 0;
printf("\n\n/******基于最少转乘次数而后最少时间******/\n");
printf("最短路径为:\n");
while(preStation != -1)
{
printf("%4d -> %4d : ",preStation+1,crtStation+1);
printf("%4d,%4d,%4d,%4d\n",S[preStation][crtStation].busNumber,S[preStation][crtStation].directType,S[preStation][crtStation].priceType,S[preStation][crtStation].itvStation);
allCost+=P[preStation][crtStation];
crtStation = preStation;
preStation = B[preStation].path.node;
}
printf("最少转乘次数为:%3d,最小时间耗费为%3d\n",B[destinationNode].distance/10000,B[destinationNode].distance%1000-5);
printf("对应花费为:%3d\n",allCost);
}
//基于最短时间结束********************************************************************
return -1;
}
void GetA()
{
int i=0;
int busNumber = 0; //公交路数
int priceType = 0; //收费方式
int directType= 0; //方向 上行 下行 环形
int stationNum= 0;
int m=0,n=0;
int* p_Start=NULL;
while (AllStation[i++] != NULL)
{
busNumber = (int)(*((int*)AllStation[i-1])); //公交路数
priceType = (int)(*((int*)AllStation[i-1]+1)); //收费方式
directType= (int)(*((int*)AllStation[i-1]+2)); //方向 上行 下行 环形
stationNum= (int)(*((int*)AllStation[i-1]+3));
p_Start = (int*)AllStation[i-1]+4;
if (directType == -1 || directType == -2)
{
for (m=0; m < stationNum; m++)
{
for (n=m; n < stationNum; n++)
{
if(A[*(p_Start+m)-1][*(p_Start+n)-1] > (n-m)*3+5)
{
A[*(p_Start+m)-1][*(p_Start+n)-1] = (n-m)*3+5;
S[*(p_Start+m)-1][*(p_Start+n)-1].busNumber = busNumber;
S[*(p_Start+m)-1][*(p_Start+n)-1].priceType = priceType;
S[*(p_Start+m)-1][*(p_Start+n)-1].directType= directType;
S[*(p_Start+m)-1][*(p_Start+n)-1].stationNum= stationNum;
S[*(p_Start+m)-1][*(p_Start+n)-1].itvStation= n-m;
}
}
}
}
else if (directType == -3 )
{
for (m=0; m < stationNum; m++)
{
for (n=m; n < stationNum; n++)
{
int itvStation=min((n-m),(m+stationNum-n));
if(A[*(p_Start+m)-1][*(p_Start+n)-1] > itvStation*3+5)
{
A[*(p_Start+m)-1][*(p_Start+n)-1] = itvStation*3+5;
A[*(p_Start+n)-1][*(p_Start+m)-1] = A[*(p_Start+m)-1][*(p_Start+n)-1];
S[*(p_Start+m)-1][*(p_Start+n)-1].busNumber = busNumber;
S[*(p_Start+m)-1][*(p_Start+n)-1].priceType = priceType;
S[*(p_Start+m)-1][*(p_Start+n)-1].directType= directType;
S[*(p_Start+m)-1][*(p_Start+n)-1].stationNum= stationNum;
S[*(p_Start+m)-1][*(p_Start+n)-1].itvStation= itvStation;
S[*(p_Start+n)-1][*(p_Start+m)-1] = S[*(p_Start+m)-1][*(p_Start+n)-1];
}
}
}
}
else
{
for (m=0; m < stationNum; m++)
{
for (n=m; n < stationNum; n++)
{
if(A[*(p_Start+m)-1][*(p_Start+n)-1] > (n-m)*3+5)
{
A[*(p_Start+m)-1][*(p_Start+n)-1] = (n-m)*3+5;
A[*(p_Start+n)-1][*(p_Start+m)-1] = A[*(p_Start+m)-1][*(p_Start+n)-1];
S[*(p_Start+m)-1][*(p_Start+n)-1].busNumber = busNumber;
S[*(p_Start+m)-1][*(p_Start+n)-1].priceType = priceType;
S[*(p_Start+m)-1][*(p_Start+n)-1].directType= directType;
S[*(p_Start+m)-1][*(p_Start+n)-1].stationNum= stationNum;
S[*(p_Start+m)-1][*(p_Start+n)-1].itvStation= n-m;
S[*(p_Start+n)-1][*(p_Start+m)-1] = S[*(p_Start+m)-1][*(p_Start+n)-1];
}
}
}
}
}
}
void GetTT()
{
int m=0,n=0;
for (m=0; m < N; m++)
{
for (n=0; n < N; n++)
{
if (A[m][n] != NON_DIRCTION_LINK)
{
TT[m][n].timeCost = A[m][n]; //时间花费
TT[m][n].preStation = m; //前一站
TT[m][n].step = 10000; //阶数
TT[m][n].busNumber = S[m][n].busNumber; //公交路数
TT[m][n].directType = S[m][n].directType; //方向 上行 下行 环形 1 2 3 4
TT[m][n].priceType = S[m][n].directType; //收费方式 10 11 13
}
else
{
TT[m][n].step = NON_DIRCTION_LINK;
}
}
}
}
void GetTans()
{
int m=0,n=0;
for (m=0; m < N; m++)
{
for (n=0; n < N; n++)
{
if (A[m][n] != NON_DIRCTION_LINK)
{
Trans[m][n] = 1;
}
else
{
Trans[m][n] = NON_DIRCTION_LINK;
}
}
}
}
void GetTansTime()
{
int m=0,n=0;
for (m=0; m < N; m++)
{
for (n=0; n < N; n++)
{
if (TT[m][n].timeCost != NON_DIRCTION_LINK)
{
TransTime[m][n] = TT[m][n].timeCost+TT[m][n].step;
}
else
{
TransTime[m][n] = NON_DIRCTION_LINK;
}
}
}
}
void Init()
{
for(int i=0;i<N;i++)
{
for(int j=0;j<N;j++)
{
if(i==j)
{
A[i][j]=5;
}
else
{
A[i][j]=NON_DIRCTION_LINK;
}
}
}
}
void GetP()
{
for (int m=0; m<N; m++)
{
for (int n=0; n<N; n++)
{
switch(S[m][n].priceType)
{
case -10:
P[m][n]=1+S[m][n].itvStation/20;
break;
case -11:
P[m][n]=1;
break;
case -13:
P[m][n]=3;
break;
default:
P[m][n]=MAXPRICE;
}
}
}
}⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -