图的应用-最短路径求解

图的最短路径

  图的最短路径是一个起点到一个终点之间最短的路径。
  用于解决最短路径问题的算法被称做“最短路径算法”， 有时被简称作“路径算法”。

Dijkstra（迪杰斯特拉）算法

介绍

  Dijkstra算法是典型的最短路径路由算法，用于计算一个节点到其他所有节点的最短路径。主要特点是从起始点开始，采用贪心算法的策略，每次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止。

实现过程

1. 初始化一个Final数组，全部设置为0，用于表示节点到某个顶点,是否已经求得了最短路径的标记，如果已有则标记为1；
2. 声明一个D数组，表示节点到某个顶点的路径；
3. 声明一个P数组，表示当前结点的前驱顶点的下标；
4. 初始化 Final、D,P数组；
5. 初始化min为无穷大，遍历 D 数组 找到对应最小权值min的顶点，记录对应下标k，标记Final[k] = 1,表明找到最短路径;
6. 之后通过顶点向外扩散找到有关联边的顶点更新D数组，若!final[w] && min + G.arc[k][w] < D[w]，则取 min + G.arc[k][w] 更新D[w]，更新P[w] = k;
7. 遍历 到 ,重复上两条操作直到final数组全部为1,求得到其他顶点的最短路径。

代码

    /*
    G；网图
    v0: v0开始的顶点
    p[v]:前驱顶点下标
    D[v]:表示从v0到vw的最短路径长度和
   */
  void ShortestPath_Dijkstra(MGraph G, int v0, Patharc *P, ShortPathTable *D)
  {
  int v,w,k,min;
  k = 0;
  int final[MAXVEX];
  final[0] = 1;

  for(v = 0; v < G.numVertexes;v++){
      final[v] = 0;
      (*D)[v] = G.arc[0][v];
      (*P)[v] = 0;
  }
  (*D)[v0] = 0;
  final[v0] = 1;
  (*P)[v0] = -1;

  for (v = 1; v < G.numVertexes; v++)
  {
      min = INFINITYC;
      for (w = 0; w < G.numVertexes; w++)
      {
           if (final[w] != 1 && (*D)[w] < min)
           {
               //下标
               k = w;
               //最小权值 
               min = (*D)[w];
           }
      }
      final[k] = 1;
      for (w = 0; w < G.numVertexes; w++)
      {
          if (final[w] != 1 && min + G.arc[k][w] < ( *D)[w])
          {
              (*D)[w] =  min + G.arc[k][w];
              (*P)[w] =  k;
          }
      }
  }

}

Floyd（弗洛伊德）算法

介绍

  Floyd算法又称为插点法，是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法，

核心原理

• 路径矩阵
    通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。
• 状态转移方程
  

实现过程

1. 把图用邻接矩阵D表示出来,定义一个矩阵P用来记录所插入点的信息;
2. 初始化P,P[v][w]表示从到需要经过的点，P[v][w]=w;
3. 对于每一对顶点 v 和 w，看看是否存在一个顶点 k 使得从 v 到 k 再到 w 比已知的路径更短。如果是更新D[v,w],各个顶点插入图中，比较插点后的距离与原来的距离，D[v][w] = min( D[v][w], D[v][k]+D[k][w] )，如果D[v][w]的值变小，则P[v][w]=k。
4. 在D中包含有两点之间最短道路的信息，而在P中则包含了最短通路径的信息。

代码

 /* 
 Floyd算法，求网图G中各顶点v到其余顶点w的最短路径P[v][w]及带权长度D[v][w]。
 Patharc 和 ShortPathTable 都是二维数组;
 */
void ShortestPath_Floyd(MGraph G, Patharc *P, ShortPathTable *D)
{
    int v,w,k;
    for (v = 0; v < G.numVertexes; v++)
    {
        //把图用邻接矩阵D表示出来
        for (w = 0; w < G.numVertexes; w++)
        {
            //把图用邻接矩阵D表示出来
            (*D)[v][w] = G.arc[v][w];
            //P[v][w]表示从$V_v$到$V_w$需要经过的点，`P[v][w]=w`
            (*P)[v][w] = w;
        } 
    }

    for (k = 0; k < G.numVertexes; k++)
    {
        for (v = 0; v < G.numVertexes; v++)
        {
            for (w = 0; w < G.numVertexes; w++)
            {
                if ((*D)[v][w] > (*D)[v][k] + (*D)[k][w] )
                {
                    (*D)[v][w] = (*D)[v][k] + (*D)[k][w];
                    (*P)[v][w] = k;
                }
            }
        }
    }
}