C++ 求最短路径问题之Dijkstra算法（二）

今天药忘吃喽~ 2022-06-13 07:57 158阅读 0赞

**求最短路径问题之Dijkstra算法（二）**

**（4）、Dijkstra算法求解实际问题**

之前讲的是最基本的Dijkstra算法，那么平时考试笔试等遇到的题目肯定不会这么“裸”，更多时候会出现这样一种情况，即从起点到终点的最短距离最小的路径不止一条。

那么碰到这种两条以上可以达到最短距离的路径，题目就会给出一个第二标尺（第一标尺是距离），要求在所有最短路径中选择第二标尺最优的一条路径，而第二标尺常见的是以下三种出题方法或者其组合：

1.  给每条边在增加一个边权（比如说花费），然后要求在最短路径有多条时要求路径上的花费之和最小（当然如果边权是其它含义，也可以是最大）
2.  给每个点增加一个点权（例如每个城市能收集到的物资），然后在最短路径有多条时要求路径上的点权之和最大（当然如果是其它含义，也可以是最小）
3.  直接问有多少条最短路径

**解决思路：**都只需要增加一个数组来存放新增的边权或点权或最短路径条数，然后在Dijkstra算法中修改优化d\[v\]的那个步骤即可，其它部分不需要改动。

如下：

1.  新增边权。以新增的边权代表花费为例，用cost\[u\]\[v\]表示u->v的花费（由题目输入），并增加一个数组c\[\]，令从起点s到达顶点u的最少花费为c\[u\]，初始化时只有c\[s\]=0，其余均为INF（一个很大的值），这样就可以在更新d\[v\]时更新c\[v\]. 代码如下：

for(int v=0; v<n; v++)
    {
         if(vis[v]==false && G[u][v]!=INF)
         {
              if(d[u]+G[u][v] < d[v])
              {
                   d[v] = d[u]+G[u][v];
                   c[v] = c[u] + cost[u][v]; 
              }
              else if(d[u]+G[u][v] == d[v] && c[u]+cost[u][v] < c[v])
                   c[v]=c[u]+cost[u][v];          //最短距离相等时看能都使c[v]更优
         }
    }

1.  新增点权。以新增的点权代表城市中能收集到的物资为例，用weight\[u\]表示城市u中的物资数目（由题目输入），并增加一个数组w\[\]，令起点s到达顶点u可以收集到的最大物资为w\[u\]，初始化时只有w\[s\]为weight\[s\],其余均为0，这样就可以在更新d\[v\]时更新w\[v\].代码如下：

for(int v=0; v<n; ++v)
    {
         if(vis[v]==false && G[u][v]!=INF)
         {
              if(d[u]+G[u][v] < d[v])
              {
                   d[v] = d[u]+G[u][v];
                   w[v] = w[u]+weight[u][v]; 
              }
              else if(d[u]+G[u][v] == d[v] && w[u]+weight[u][v]>w[v])
                   w[v] = w[u]+weight[u][v];
         }
    }

1.  求最短路径条数。只需要添加一个数组num\[\]，令从起点s到达顶点u的最短路径条数为num\[u\]，初始化时只有num\[s\]=1，其余均为0，这样就可以在更新d\[v\]时让num\[v\]=num\[u\]，而当d\[u\]+G\[u\]\[v\] =d\[v\]时，让num\[v\]+=num\[u\].代码如下：

for(int v=0; v<n; ++v)
    {
         if(vis[v]==false && G[u][v]!=INF)
         {
              if(d[u]+G[u][v] < d[v])
              {
                   d[v] = d[u]+G[u][v];
                   num[v]=num[u];
              }
              else if(d[u]+G[u][v] == d[v] && w[u]+weight[u][v]>w[v])
                   num[v]+=num[u];
         }
    }

以上是不是很简单呢？？？