关于数据结构中最短路径问题

Question

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,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]);
}}
在运行过程中没有根据给定shu'ju计算路径，总是输出上限值是什么情况，这一部分有没有错误

Answer 1

问题 1: åˆ›å»ºæ™¯ç‚¹å›¾çš„函数initgraph()里,因为邻接矩阵是对称矩阵,所以要对称赋值,
        å¿…须是用语句 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 introduction[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;
}