无权双向图中最短路径和次短路径的区别

在图论领域中，无权双向图是对各种真实世界情境进行建模的基本框架。这些图可以让我们探索不同实体之间的关系，比如道路网络或社交关系。一个吸引我们注意力的核心方面是找到两个节点之间的路径并确定它们的长度。在本文中，我们深入探讨这个主题的一个有趣方面-理解无权双向图中最短路径和次短路径之间的区别。

最短路径和次短路径

无权双向（或无向）图由连接的顶点或节点组成。这些边没有具体的权重或距离，而只是表示存在连接，没有方向性偏好。

路径表示一系列相互连接的顶点，其中每个顶点通过边直接连接到其相邻的顶点。在这里，我们专注于找到连接两个不同的明确称为源节点和目标节点的顶点的路径，同时通过最小总边遍历来确定它们的长度。

最短路径

找到最短路径的概念因其在计算机科学学科中的广泛应用而受到重视，如网络算法或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。

用C++程序找出最短路径和第二短路径之间的差值

为了最优地解决这个问题，我们将利用修改过的Dijkstra算法来获取不仅一个，而是两个最小距离。

步骤

步骤1 - 初始化必要的数据结构，包括邻接矩阵或链表表示法。
步骤2 - 基于距离值（最小在顶部）创建优先队列或最小堆数据结构。
步骤3 - 将所有距离初始化为无穷大，除了源顶点’s’，它应该是零。
步骤4 - 将参数distance[s]和’s’插入到优先队列或堆中。
步骤5 - 当优先队列/堆不为空时 –
- 从优先队列/堆中提取顶点’u’
- 对于与u相邻的每个邻居顶点v –
  - 更新distance[v] = distance[u] + 1
  - 将(distance[v], v)插入到优先队列/堆中
步骤6 - 在整个图被处理完毕后，距离数组将存储从源顶点’s’到所有其他顶点的最短路径。

代码

//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;
}