好资源导航 » 文章资讯 » 具有恰好 k 条边的最短路径

具有恰好 k 条边的最短路径

2023-06-21 06:31:03 83

一个有向图提供了每对顶点之间的权重，并且还提供了两个顶点u和v。我们的任务是找到从顶点u到顶点v的最短距离，恰好有k条边。

为了解决这个问题，我们将从顶点u开始，遍历所有相邻的顶点，并使用k值作为k-1对相邻顶点进行递归。

输入和输出

Input:
The cost matrix of the graph.
0 10 3 2
∞  0 ∞ 7
∞  ∞ 0 6
∞  ∞ ∞ 0

Output:
最短路径的权重为 9

算法

shortKEdgePath(u, v, edge)

输入-顶点u和v，以及一些边。

输出-最短路径的距离。

Begin
   if edge = 0 and u = v, then
      return 0
   if edge = 1 and cost[u, v] ≠ ∞, then
      return cost[u, v]
   if edge <= 0, then
      return ∞
   set shortPath := ∞

   for all vertices i, do
      if cost[u, i] ≠ ∞ and u ≠ i and v ≠ i, then
         tempRes := shortKEdgePath(i, v, edge - 1)
         if tempRes ≠ ∞, then
            shortPath = minimum of shortPath and (cost[u,i]+tempRes
   done
   return shortPath
End

示例

#include 
#define NODE 4
#define INF INT_MAX
using namespace std;

int cost[NODE][NODE] = {
   {0, 10, 3, 2},
   {INF, 0, INF, 7},
   {INF, INF, 0, 6},
   {INF, INF, INF, 0}
};

int minimum(int a, int b) {
   return (a输出结果最短路径的权重为 9

返回顶部
514930285
czq8825@qq.com

具有恰好 k 条边的最短路径

输入和输出

算法

示例

热门推荐

随机推荐