关于数据结构中最短路径问题
发布网友
发布时间：2022-04-23 02:16
共1个回答
热心网友
时间：2023-09-19 16:37
必须是用语句 c->arcs[j][i].adj=c->arcs[i][j].adj;
注意,是[j][i]在前, 而[i][j]在后.
而不是c->arcs[i][j].adj=c->arcs[j][i].adj;//错误
问题 2: 函数allpath()能计算出最短路径的总线路长度,但是,显示的中途经过的顶点不对.
代码的修改方案:
对于"任意一点与其它各点的最短路径"的问题,
可以用迪杰斯特拉(Dijkstra)算法,也可以用弗洛伊德(Floyd)算法,
以下是修改后的代码,提供两个方案:
void allpath_Floyd(mgraph c) //方案1:Floyd算法
void allpath_Dijkstra(mgraph c) //方案2:Dijkstra算法
如果有任何问题,可以百度私信给我.
#include "stdio.h"
#include "string.h"
#define Infinity 9999
#define MaxVertexNum 20
typedef struct arcell //边的信息
{
int adj; //权值
}arcell,adjmatrix[MaxVertexNum][MaxVertexNum];
typedef struct vexsinfo //顶点信息
{
int position; //景点的编号
char name[32]; //景点名
char introction[56]; //景点的介绍
}vexsinfo;
typedef struct mgraph//使用邻接矩阵实现图的存储
{
vexsinfo vexs[MaxVertexNum];//数组顶点向量,存顶点信息
adjmatrix arcs; //邻接矩阵
int vexnum,arcnum; //顶点数和边数
}mgraph;
mgraph c; //全局变量
//创建景点图 (输入参数是指针)
void initgraph(mgraph *c)
{
int i,j;
c->vexnum=6; //顶点的总数量
c->arcnum=8; //边的总数量
for(i=0;i<c->vexnum;i++)//设置顶点编号
{
c->vexs[i].position=i;
}
strcpy(c->vexs[0].name,"v1");
strcpy(c->vexs[1].name,"v2");
strcpy(c->vexs[2].name,"v3");
strcpy(c->vexs[3].name,"v4");
strcpy(c->vexs[4].name,"v5");
strcpy(c->vexs[5].name,"v6");
//先初始化图的邻接矩阵
for(i=0;i<c->vexnum;i++)
{
for(j=0;j<c->vexnum;j++)
{
c->arcs[i][j].adj=Infinity;
}
}
c->arcs[0][1].adj=7;
c->arcs[0][2].adj=11;
c->arcs[1][2].adj=10;
c->arcs[1][3].adj=9;
c->arcs[2][3].adj=5;
c->arcs[2][4].adj=7;
c->arcs[2][5].adj=8;
c->arcs[4][5].adj=6;
//邻接矩阵是对称矩阵,对称赋值
for(i=0;i<c->vexnum;i++)
{
for(j=0;j<c->vexnum;j++)
{
//注意,是[j][i]在前, 而[i][j]在后.
c->arcs[j][i].adj=c->arcs[i][j].adj;
}
}
}
//查看景点间的路线 [需要改善]
void allpath(mgraph c)
{
//求从顶点v0到其余顶点的最短路径p[]及带权长度d[v]（最短路径的距离）
//p[][]数组用于存放两顶点间是否有通路标识，如果p[v][w]=1，则w是从v0到v的最短路径上的顶点
//visited[数组用于设置访问标志
int v,w,i,min,t=0,x; //变量t没有使用
int v0;//v0为起始景点的编号
int visited[20],d[20],p[20][20];
printf("\n请输入一个起始景点的编号:");
scanf("%d",&v0);
printf("\n\n");
while(v0<0 ||v0>c.vexnum)
{
printf("\n您输入的景点不存在\n");
printf("请重新输入：");
scanf("%d",&v0);
}
for(v=0;v<c.vexnum;v++)
{
visited[v]=0;//初始化各个景点的访问标识
d[v]=c.arcs[v0][v].adj;//v0到各顶点v的权值赋给d[v],arcs是临界矩阵存两景点间的信息
for(w=0;w<c.vexnum;w++)
p[v][w]=0;//初始化数组，各顶点之间的路径全部设置为空
if(d[v]<Infinity)//v0到v有边相连，修改p[v][w]的值为1
{
p[v][v0]=1;
p[v][v]=1;//各顶点到自己要联通
}
}
d[v0]=0;//自己到自己的权值设置为0
visited[v0]=1;
for(i=1;i<c.vexnum;i++)//对其余c.vexnum-1个顶点w，一次求v到w的最短路径
{
min=Infinity;
for(w=0;w<c.vexnum;w++)
if(!visited[w])
if(d[w]<min)
{
v=w;min=d[w];
}
visited[v]=1;
for(w=0;w<c.vexnum;w++)
if(!visited[w]&&(min+c.arcs[v][w].adj<d[w]))//v到 w有边相连
{
d[w]=min+c.arcs[v][w].adj;//修改v0到w的权值d[w]
for(x=0;x<c.vexnum;x++)//所有v0到v的最短路径都是v0到w的最短路径上的顶点
p[w][x]=p[v][x];
p[w][w]=1;
}}
for(v=0;v<c.vexnum;v++)//输出v0其它景点v的最短路径
{
if(v0!=v)
printf("%s",c.vexs[v0].name);//输出景点v0的名称
for(w=0;w<c.vexnum;w++)//对图中每个顶点w，试探w是否是v0到v的最短路径上的顶点
{
if(p[v][w] &&w!=v0 && w!=v)//如果w是且不等于v0，则输出该景点
printf("---->%s",c.vexs[v].name);
}
printf("---->%s",c.vexs[v].name);
printf("\n总路线长为%d米:\n\n",d[v]);
}
}
//输出任意一点与其它各点的最短路径
//算法: 弗洛伊德(Floyd)
void allpath_Floyd(mgraph c)
{
int v,w,k;
int v0; //输入的起始顶点编号
int P[MaxVertexNum][MaxVertexNum]; //二维数组P用于记录两点之间的路径下标
int D[MaxVertexNum][MaxVertexNum]; //二维数组D用于记录每条边的权值(也就是距离)
while(1)
{
printf("请输入一个起始景点的编号(%d到%d): ",0,c.vexnum-1);
scanf("%d",&v0);
//景点图有c.vexnum个顶点,编号从0到(c.vexnum-1)
if(v0<0 || v0 >= c.vexnum)
{
printf("景点的编号不存在!请重新输入编号\n");
continue; //直接跳到while()语句,继续循环
}
else
{
break;
}
}
//对数组D和数组P进行初始化
for(v=0; v < c.vexnum; v++)
{
for(w=0; w < c.vexnum; w++)
{
D[v][w]=c.arcs[v][w].adj; //D[v][w]填入的初始值就是每条边的权值(也就是距离)
P[v][w]=w; //P默认填入顶点编号w,作为终点
}
}
//Floyd算法的核心代码: 3层for循环
//最外层的k是中间点, v是起点, w是终点
for(k=0; k<c.vexnum; ++k)
{
for(v=0; v<c.vexnum; ++v)
{
for(w=0; w<c.vexnum; ++w)
{
if ( D[v][w] > (D[v][k]+D[k][w]) )
{
//如果经过下标为k顶点路径比原两点间路径更短,
//那么,就将当前两点间权值设为更小的一个路径设置为经过下标为k的顶点
D[v][w]=D[v][k]+D[k][w];
P[v][w]=P[v][k];
}
}
}
}
v=v0; //v0是起始顶点编号
for(w=0; w<c.vexnum; w++) //遍历所有顶点
{
if(v==w)
{
continue;
}
k=P[v][w]; //获得"第一个"路径顶点下标
printf("%s",c.vexs[v].name); //打印"起点"的名称
while(k!=w) //如果路径顶点下标不是终点
{
printf("-->%s",c.vexs[k].name); //打印路径"经过的顶点"的名称
k=P[k][w]; //获得"下一个"路径顶点下标
}
printf("-->%s",c.vexs[w].name); //打印"终点"的名称
printf(" 总路线长%dm",D[v][w]);
printf("\n\n");
}
}
//输出任意一点与其它各点的最短路径
//算法: 迪杰斯特拉(Dijkstra)
void allpath_Dijkstra(mgraph c)
{
int v0; //输入的起始顶点编号
int w0;
int v,w,k,min;
int qty;
int finalData[MaxVertexNum]; //finalData[w]=1表示已经求得起始顶点v0到vw(w是下标)的最短路径
int P[MaxVertexNum]; //数组P用于记录两点之间的路径下标
int D[MaxVertexNum]; //数组D用于存储到各点最短路径的权值和
int PathBuf[MaxVertexNum]; //存入按顺序的路径下标(用于屏幕显示)
while(1)
{
printf("请输入一个起始景点的编号(%d到%d): ",0,c.vexnum-1);
scanf("%d",&v0);
//景点图有c.vexnum个顶点,编号从0到(c.vexnum-1)
if(v0<0 || v0 >= c.vexnum)
{
printf("景点的编号不存在!请重新输入编号\n");
continue; //直接跳到while()语句,继续循环
}
else
{
break;
}
}
for(v=0; v < c.vexnum; v++) //初始化数据
{
finalData[v] = 0; //全部顶点初始化为未知最短路径状态
D[v] = c.arcs[v0][v].adj; //将与v0点有连线的顶点加上权值
P[v] = 0; //初始化路径数组P为0
}
D[v0] = 0; //v0至v0路径为0
finalData[v0] = 1; //等于1,就是表示v0至v0不需要求路径
//开始主循环, 每次求得v0到某个v顶点的最短路径
for(v=0; v < c.vexnum; v++)
{
if(v==v0) continue;
min=Infinity; //当前所知道的离v0顶点的最短距离
for(w=0; w < c.vexnum; w++) //寻找离v0最近的顶点
{
//如果finalData[w]等于0,表示下标w的顶点还没有找到最短路径
if(finalData[w]==0 && D[w]<min)
{
k = w;
min = D[w]; //w顶点离v0顶点更近,暂时将其设为最短距离
}
}
finalData[k] = 1; //将目前找到的最近的顶点置为1,表示已经找到最短路径
for(w=0; w < c.vexnum; w++) //遍历所有顶点,修正当前最短路径及距离
{
//如果经过v顶点的路径比现在这条路径的长度短的话,
//说明找到了更短的路径, 修改数值D[w]和P[w]里的值
if(finalData[w]==0 && ( min+c.arcs[k][w].adj < D[w] ))
{
D[w] = min + c.arcs[k][w].adj; //修改当前路径长度
P[w] = k;
}
}
}
//执行完Dijkstra算法之后,一维数组P[]里存放的最短路径是"倒序"的,
//所以,先用数组PathBuf[]将"倒序"的路径存放起来,
//然后,从数组PathBuf[]的末尾开始打印,这样,屏幕显示的就是"正向顺序"的路径.
for(w0=0 ; w0<c.vexnum ; w0++)
{
if(w0==v0)
{
continue;
}
qty=0;
PathBuf[qty]=w0; //w0是最短路 径的"最后一个顶点"的下标
qty++;
k=w0;
while(P[k]!=0)
{
PathBuf[qty]=P[k]; //最短路径里的"中间顶点"的下标
qty++;
k=P[k];
}
PathBuf[qty]=v0; //v0是最短路径的"第一个顶点"的下标
qty++; //最后的qty就是等于最短路径里的顶点数量
//重新按"正向顺序",打印最短路径里的所有顶点
//从数组的末尾开始打印
for(k=qty-1 ;k>=1 ; k--)
{
printf("%s-->",c.vexs[PathBuf[k]].name);
}
printf("%s",c.vexs[PathBuf[k]].name);
printf(" 总路线长%dm",D[w0]);
printf("\n\n");
}
}
int main(void)
{
//创建景点图
initgraph(&c); //输入参数是指针
//查看景点间的路线
allpath_Floyd(c); //方案1: Floyd算法
//allpath_Dijkstra(c); //方案2: Dijkstra算法
//allpath(c); //原代码[需要改善]
return 0;
}
