大话数据结构---（六）最短路径算法

Nina ·

更新时间:2024-09-21

· 814 次阅读

1.Dijkstra算法

Dijkstra算法解决了从某个源点到其余各顶点的最短路径问题，结合图1举个例子，从V1到V2的最短路径，并不是直接连接V1,V2,而是先经过V0再到V2，好，下面一起来看代码。在这里插入图片描述

#define MAXVEX 9
#define INFINITY 65535
typedef int Patharc[MAXVEX];//用于存储最短路径下标的数组
typedef int ShortPathTable[MAXVEX];//用于存储到各点最短路径的权值和
//Dijkstra算法，求有向网G的v0顶点到其余顶点v最短路径P[v]即带权长度D[v]
//P[v]的值为前驱顶点下标，D[V]表示v0到v的最短路径长度和
void ShorttestPath_Dijkstra(MGraph G,int v0,Paththarc *P,ShortPathTable *D)
{
   int v,w,k,min;
   int final[MAXVEX];//final[w]=1表示求得顶点v0至vw的最短路径
   for(v=0;v<G.numVertexes;v++)
   {
     final[v]=0;//全部顶点初始化为未知最短路径状态
     (*D)[v]=G.arc[v0][v];//将与v0点有连线的顶点上加上权值
     (*P)[v]=0;//初始化路径数组P为0
   }
   (*D)[v0]=0;
   final[v0]=1;//v0至v0不需要求路径
   //开始主循环，每次求得v0到某个v顶点的最短路径
   for(v=1;v<G.numVertexes;v++)
   {
     min=INFINITY;//当前所知离v0顶点的最近距离
     for(w=0;w<G.numVertexes;w++)//寻找离v0最近的顶点
     {
       if(!final[w]&&(*D)[w]<min)
       {
         k=w;
         min=(*D)[w];//w顶点离v0顶点更近
       }
     }
     final[k]=1;//将目前找到的最近的顶点置为1
     for(w=0;w<G.numVertexes;w++)//修正当前最短路径及距离
     {
       //如果经过v顶点的路径比现在这条路径的长度短的话
       if(!final[w]&&(min+G.arc[k][w]<(*D)[w]))
       {
         //说明找到了更短的路径，修改D[w]和P[w]
         (*D)[w]=min+G.arc[k][w];//修改当前路径长度
         (*P)[w]=k;
       }
     }
   }
}

2.Floyed算法

如果我们需要知道任意顶点到其余所有顶点的最短路径怎么办呢？现在再来介绍另一个求最短路径的算法—弗洛伊德，它求所有顶点到所有顶点的时间复杂度也是（O3），但其算法非常简单优雅，能让人感觉到智慧的无限魅力，它的思想可以简单概述为,借助辅助点，减小路径，算法代码如下。

typedef int Pathmatirx[MAXVEX][MAXVEX];
typedef int ShortPathTable[MAXVEX][MAXVEX];
//Floyed算法，求网图G中各顶点v到其余顶点w最短路径P[v][w]及带权长度D[v][w]
void ShorttestPath_Floyd(MGraph G,Pathmatirx *P,ShortPathTable *D)
{
  int v,w,k;
  for(v=0;v<G.numVertexes;v++)
  {
    //初始化D与P
    for(w=0;w<G.numVertexes;w++)
    {
     (*D)[v][w]=G.matirx;//D[v][w]值即为对应点间的权值
     (*P)[v][w]=w;//初始化P
    }
  }
  for(k=0;k<G.numVertexes;k++)
  {
   for(v=0;v<G.numVertexes;v++)
   {
    for(w=0;w<G.numVertxes;w++)
    {
     if((*D)[v][w]<(*D)[v][k]+(*D)[k][w])
     {
       //如果经过下标为k顶点路径比原两点间路径更短
       //将当前两点间权值设为更小的一个
       (*D)[v][w]=(*D)[v][k]+(*D)[k][w];
       (*P)[v][w]=(*P)[v][k];//路径设置经过下标为k的顶点
     }
    }
   }
  }
}

求最短路径的显示代码可以这样写

for(v=0;v<G.numVertexes;v++)
{
  for(w=v+1;w<G.numVertexes;w++)
  {
    cout<<v<<","<<w<<":"<<D[v][w]<<endl;
    k=P[v][w];//获得第一个路径顶点下标
    cout<<"path"<<v;//打印源点
    while(k!=w)
    {
      cout<"<<k;//打印路径顶点
      k=P[k][w];//获得下一个路径顶点下标
    }
    cout<"<<w;//打印终点
  }
  cout<<endl;
}

如果你面临需要求所有顶点至所有顶点的最短路径问题时，弗洛伊德算法应该是不错的选择。

作者：赶路的苟狗

大话数据结构数据最短路径算法最短路径算法数据结构

1024 个赞