無權雙向圖中最短路徑和次短路徑的差異

介紹

在圖論領域，無權雙向圖構成了對各種現實世界場景建模的基本框架。這些圖允許我們探索不同實體之間的關係，例如道路網路或社會聯絡。一個吸引我們注意力的關鍵方面是在兩個節點之間尋找路徑並確定它們的長度。在本文中，我們將深入探討該主題的一個有趣方面——理解無權雙向圖中最短路徑和次短路徑之間的區別。

最短路徑和次短路徑

無權雙向（或無向）圖由透過邊連線的頂點或節點組成。這些邊沒有分配任何特定的權重或距離，而只是表示存在連線，沒有任何方向性偏差。

路徑表示一系列相互連線的頂點，其中每個頂點都透過邊直接連線到其相鄰的頂點。在這裡，我們關注的是尋找連線兩個明確稱為源節點和目標節點的不同頂點的路徑，這些路徑具有最小的總邊遍歷次數。

最短路徑

尋找最短路徑的概念因其在計算機科學領域（如網路演算法或 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。

方法 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' 到所有其他頂點的最短路徑。

示例

//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 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告