无权双向图中最短路径和次短路径的差异

介绍

在图论领域，无权双向图构成了对各种现实世界场景建模的基本框架。这些图允许我们探索不同实体之间的关系，例如道路网络或社会联系。一个吸引我们注意力的关键方面是在两个节点之间寻找路径并确定它们的长度。在本文中，我们将深入探讨该主题的一个有趣方面——理解无权双向图中最短路径和次短路径之间的区别。

最短路径和次短路径

无权双向（或无向）图由通过边连接的顶点或节点组成。这些边没有分配任何特定的权重或距离，而只是表示存在连接，没有任何方向性偏差。

路径表示一系列相互连接的顶点，其中每个顶点都通过边直接连接到其相邻的顶点。在这里，我们关注的是寻找连接两个明确称为源节点和目标节点的不同顶点的路径，这些路径具有最小的总边遍历次数。

最短路径

寻找最短路径的概念因其在计算机科学领域（如网络算法或 GPS 路线规划系统）的广泛应用而受到广泛关注。最短路径是指从给定的源节点到其对应的目标节点的最直接的顶点序列，具有最小的边遍历次数。

换句话说，它描述的是与无权双向图中存在的替代路线相比，连接边较少的行程。存在各种用于计算这些最小路径的算法；一个值得注意的例子是 Dijkstra 算法，它即使在处理大型图时也能确保效率。

次短路径

关键的区别在于遍历边的数量。虽然两条路径都旨在连接相同的源节点和目标节点，但它们在边的利用方面有所不同。次短路径保证它仍然表示两个节点之间的有效连接，同时有意排除与最短路径的任何重叠。这种排除意味着主最短路径中使用的至少一条边将在此替代路线中被避免。

虽然乍一看这似乎违反直觉，但理解这些区别存在的原因可以帮助我们探索无权双向图中更有效和多样化的路由可能性。

示例

我们有一个具有 n=4 个节点和 m=4 条边的无向图。边连接可以描述如下：

arr[0] = {1, 2}
arr[1] = {2, 3}
arr[2] = {3, 4}
arr[3] = {1, 4}

我们的目标是找到从节点“1”到节点“4”的最短路径的长度，并计算其与次短路径长度的差值。在下面的代码中，上述图的最短路径是：

1 -> 2-> 3 -> 4

次短路径是：

1 -> 4

最短路径的长度是 3，次短路径的长度是 2，所以它们之间的差值是 1。

Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.

方法 1：查找最短路径和次短路径之间差异的 C++ 程序

为了最佳地解决这个问题，我们将使用 Dijkstra 算法，该算法经过修改后不仅可以检索一个最小距离，还可以检索两个最小距离。

算法

  • 步骤 1 - 初始化必要的数据结构，包括邻接矩阵或链表表示。

  • 步骤 2 - 根据距离值（最小值在顶部）创建一个优先队列或最小堆数据结构。

  • 步骤 3 - 从将所有距离设置为无限大（除了源顶点 's'，应为零）开始。

  • 步骤 4 - 将参数作为 distance[s] 和 ‘s’ 插入到优先队列或堆中。

  • 步骤 5 - 当优先队列/堆不为空时 -

    • 从优先队列/堆中提取顶部顶点 'u'

    • 对于与 u 相邻的每个相邻顶点 v -

      • 更新 distance[v] = distance[u] + 1

      • 将 (distance[v], v) 插入到优先队列/堆中

  • 步骤 6 - 处理完整个图后，distances 数组将存储从源顶点 's' 到所有其他顶点的最短路径。

示例

Open Compiler
//Including the required header files
#include <iostream>
#include <vector>
#include <queue>
#include <limits>

using namespace std;

const int INF = numeric_limits<int>::max();
//Declaring the function with three arguments
int shortestDifference(int numNodes, int numEdges, vector<pair<int,int>>& edges) {
   vector<vector<int>> adjacency(numNodes+1);
   for(auto& edge : edges) {
      adjacency[edge.first].push_back(edge.second);
      adjacency[edge.second].push_back(edge.first); // since it is an undirected graph
   }

   priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;

   vector<int> dist(numNodes+1, INF);

   const int source = 1; // Start node

   dist[source] = 0;

   pq.push({dist[source],source});

   while(!pq.empty()) {
      int currentDistance=pq.top().first;
      int currentNode=pq.top().second;

      pq.pop();

      if(currentDistance>dist[currentNode])
      continue;

      for(auto neighbor:adjacency[currentNode]) {
         if(dist[neighbor]>currentDistance+1) {
            dist[neighbor]=currentDistance+1;
            pq.push({dist[neighbor],neighbor});
         }
      }
   }

   return abs(dist[numNodes]-2*dist[4]);
}

// Testing the code with the required input 

int main() {
   vector<pair<int,int>> edges={{0,0}, {1,2}, {2,3}, {3,4}, {1,4}};
   int numNodes = 4;
   int numEdges = 5;
   cout << shortestDifference(numNodes, numEdges, edges) << endl;
}

输出

1

结论

前者通过最小化边遍历次数来建立最佳连接，而无需考虑替代方案。另一方面，后者通过提供替代路线来拥抱多样性，同时避免与其较短的对应物重叠的边。掌握这些概念使我们能够构建适用于各种领域的强大算法，例如网络优化或导航系统，使我们能够释放图论研究中的新潜力。

更新于：2023年8月25日

134 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告