求图的任意两点的最短路径有Dijkstra算法和Floyd算法

截屏2020-05-19下午10.31.46.png

Dijkstra算法

思路：构建D和P两个数组，分别表示V0 到某个顶点Vw的路径和当前顶点的前驱顶点的下标

截屏2020-05-19下午10.41.13.png

截屏2020-05-19下午11.11.04.png

实现代码

/*用于存储最短路径下标的数组*/
typedef int Patharc[MAXVEX];
/*用于存储到各点最短路径权值的和*/
typedef int ShortPathTable[MAXVEX];

/*
G: 网图;
v0: V0开始的顶点;
p[v]: 前驱顶点下标;
d[v]: 表示从V0到V的最短路径长度和;
*/
void ShortestPath_Dijkstra(MGraph G, int v0, Patharc *p, ShortPathTable *d){
  int min, k = 0;
  int final[MAXVEX]; //final[w] = 1 表示求得顶点V0~Vw的最短路径
  
  //初始化数据
  for (int i = 0; i<G.numNodes; i++) {
      final[i] = 0;
      (*d)[i] = G.arc[v0][I];
      (*p)[i] = v0;
      if(i == v0){
          final[i] = 1;
          (*p)[i] = -1;
      }
  }
  
  //主循环，求的v0到某个顶点的最短路径
  for (int i = 0; i<G.numNodes; i++) {
      min = INFINITYC;
      
      for (int j = 0; j<G.numNodes; j++) {
          if (final[j] == 0 && (*d)[j] < min) {
              k = j;
              min = (*d)[j];
          }
      }
      
      final[k] = 1;
      
      for (int j = 0; j<G.numNodes; j++) {
          if (final[j] == 0 && (min + G.arc[k][j])<(*d)[j]) {
              (*d)[j] = min + G.arc[k][j];
              (*p)[j] = k;
          }
      }
  }
}

Floyd算法

思路：创建D和P两个二维数组，分别用来存储顶点直接最短路径权值和前驱顶点的下标，D数组的公式为：D[V][W] = min(D[V][W],D[V][K]+D[K][W])

22623605-8593-4192-97FB-84215C6D4C5F.png

实现代码

typedef int Floyd_Patharc[MAXVEX][MAXVEX];
typedef int Floyd_ShortPathTable[MAXVEX][MAXVEX];

//Floyd算法，求网图G中各顶点v到其余顶点w的最短路径P[v][w]及带权长度D[v][w]。
//Patharc 和 ShortPathTable 都是二维数组;
void ShortestPath_Floyd(MGraph G, Floyd_Patharc *p, Floyd_ShortPathTable *d){
  //初始化d和p矩阵
  for (int i = 0; i<G.numNodes; i++) {
      for (int j = 0; j< G.numNodes; j++) {
          (*d)[i][j] = G.arc[i][j];
          (*p)[i][j] = j;
      }
  }
  //k表示经过的中转顶点
  for (int k = 0; k<G.numNodes; k++) {
      for (int i = 0; i<G.numNodes; i++) {
          for (int j = 0; j< G.numNodes; j++) {
              if ((*d)[i][j] > (*d)[i][k] + (*d)[k][j]) {
                  (*d)[i][j] = (*d)[i][k] + (*d)[k][j];
                  (*p)[i][j] = (*p)[i][k];
              }
          }
      }
  }
}