代码如下:
//算法求解问题:算法求解的是最短路径问题,但是要经过中间节点k而且文件的输入格式难度也有所加大
//算法求解问题:算法求解的是最短路径问题,但是要经过中间节点k而且文件的输入格式难度也有所加大
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<vector>
using namespace std;
#define N 20
int ans[N][N];//定义邻接矩阵方便待会用floyd算法解出最短路径
int pre[N][N];
//floyd算法
void floyd(int n){
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(ans[i][k]==-1||ans[k][j]==-1){
continue;//如果中间结点不能连通,则继续下一个循环
}
if(ans[i][j]==-1||ans[i][j]>ans[i][k]+ans[k][j]){//如果有更短路径则更新路径值
ans[i][j]=ans[i][k]+ans[k][j];
pre[i][j]=pre[i][k];//记录路径
}
}
}
}
}
int main(){
FILE *fp1,*fp2;
char s[N];
fp1=fopen("4.in","r");
fp2=fopen("4.out","w");
for(int i=1;i<N;i++){//初始化邻接矩阵的值
for(int j=1;j<N;j++){
ans[i][j]=-1;
pre[i][j]=j;
}
ans[i][i]=0;
}
int sum=0;
while(fgets(s,99,fp1)){
sum+=1;
int head=s[0]-'0';
int i=1;
int len=strlen(s);
while(i<len){
i+=1;//跳过空格
int next=s[i]-'0';
i+=2;//跳过空格
int cost=s[i]-'0';
i++;//移动到下一个字符
if(next==0&&cost==0)break;
ans[head][next]=cost;
ans[next][head]=cost;
}
}
floyd(sum);
for(i=1;i<=sum;i++){
for(int j=1;j<=sum;j++){
printf("%d ",ans[i][j]);
}
printf("\n");
} //算法检测成功
printf("请输入您的起点,中间结点,终点:\n");
int o,p,q;
scanf("%d%d%d",&o,&p,&q);
printf("最短路径为:%d\n",ans[o][p]+ans[p][q]);
printf("具体记录为:%d ",o);
int now=pre[o][p];
while(1){
printf("%d ",now);
if(now==p)break;
now=pre[now][p];//否则向下找
}
now=pre[p][q];
while(1){
printf("%d ",now);
if(now==q)break;
now=pre[now][q];
}
return 0;
}