資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學透過新增一條邊來最大化給定頂點之間的最短路徑
在這個問題中，我們將透過在兩個選定的頂點之間新增一條邊來最大化頂點 1 到 N 之間的最短路徑。
在這裡，我們將跟蹤圖中每個節點到第 0 個和 N-1 個節點的距離。之後，我們將以某種方式在任何兩個選定的頂點之間插入一條邊，以便最大化 1 到 N 之間的最短路徑。
問題陳述 - 我們給定一個無向圖。該圖包含 N 個頂點和 M 條邊。此外，我們還給定了一個包含 K 條選定邊的 s_edges[] 陣列。我們需要透過在任何兩個選定頂點之間插入新邊來最大化頂點 1 和 N 之間的最短路徑。還給定，我們可以在已經存在邊連線的選定頂點之間插入邊。
示例
輸入
N = 6, M = 5, K = 2, s_edges[] = {1, 4}
0
/
1 5
\ /
2 - 3 - 4
輸出
3
解釋 - 在這裡，我們只有兩個選擇頂點的選項。因此，當我們在 1 和 4 之間新增邊時，我們找到距離 3。
輸入
N = 6, M = 5, K = 3, s_edges[] = {1, 4, 3}
0
/
1 5
\ /
2 - 3 - 4
輸出
5
解釋 - 在這裡，我們有 3 個選項可以在兩個頂點之間新增邊。
如果我們在 1 和 4 之間新增一條邊，最短路徑是 3。
如果我們在 1 和 3 之間新增一條邊，最短路徑是 4。
如果我們在 3 和 4 之間新增一條邊，最短路徑是 5。
在這裡，我們需要最大化最短路徑。因此，我們在 3 和 4 之間添加了一條邊。
方法
在這種方法中，我們將首先找到圖中每個節點到源節點和目標節點的距離。之後，我們將根據其到源節點和目標節點的距離之差對選定頂點進行排序。因為差異越大，意味著最短路徑的長度越長，這將有助於我們最大化最短路徑。
之後，我們將遍歷排序後的選定頂點，透過在任何兩個節點之間插入一條邊來最大化最短路徑。
演算法
步驟 1 - 定義全域性變數 edgesArray[200005] 陣列來儲存圖的邊，以及 v_dist[2][200000] 陣列來儲存每個節點到起點和終點的距離。在這裡，我們將使用 dist[0][] 來儲存到第 0 個節點的距離，並使用 dist[1][] 來儲存當前節點到目標節點的距離。
步驟 2 - 在 main() 方法中，準備一個圖。
步驟 3 - 執行 performBFS() 函式兩次，分別查詢每個節點到源節點和目標節點的距離。
步驟 3.1 - 在 performBFS() 函式中，定義 que[] 陣列並使用 fill() 方法用最大值填充陣列的所有元素。
步驟 3.2 - 定義 q_left 和 q_right 變數作為 que[] 陣列中佇列的左指標和右指標。用起點初始化 que[q_right++]，並將 v_dist[start] 初始化為 0，因為起點到自身的距離為 0。
步驟 3.3 - 使用 while 迴圈，並進行迭代，直到 q_left 小於 q_right。
步驟 3.4 - 在迴圈中，從陣列的 q_left 索引處獲取元素並將其儲存到 temp 中。同時，將 q_left 加 1。
步驟 3.5 - 使用巢狀迴圈遍歷 temp 頂點的所有邊。如果當前邊未被訪問，則使用 v_dist[temp] + 1 更新其距離，並將其插入到 que[] 陣列的 q_right 索引處。之後，將 q_right 加 1。
步驟 4 - 在找到每個節點到源節點和目標節點的距離後，定義 distDiff[] 列表來儲存每個頂點的距離差。
步驟 5 - 遍歷 s_edges[] 陣列的每個元素。接下來，將它到源節點和目標節點的距離差以及當前節點本身儲存到 'distDiff' 列表中。
步驟 6 - 根據距離差對 distDiff 列表進行排序。在這裡，我們需要在兩個頂點之間新增邊之後最大化最短距離。因此，我們需要找到排序列表中具有最大最短路徑的兩個相鄰頂點。
步驟 7 - 現在，將 'shortDist' 初始化為 0，將 'maximumDist' 初始化為最小整數值。
步驟 8 - 開始遍歷 'distDiff' 列表。獲取當前對的第二個元素，代表頂點。
步驟 9 - 如果 'shortDist' 小於 maximumDist + v_dist[1][current]，則更新 'shortDist' 值，因為我們需要最大化最短距離。
步驟 10 - 如果 'maximumDist' 小於 v_dist[0][current]，則更新 'maximumDist' 值。在這裡，'maximumDist' 儲存任何特定節點到源節點的最大距離。在下一次迭代中，我們將它新增到從當前節點到目標節點的距離，以最大化最短距離。
步驟 11 - 最後，列印 v_dist[0][N-1] 或 shortDist + 1 中較小的一個。
示例
#include <bits/stdc++.h>
using namespace std;
const int maxi = 1e9 + 7;
int N, M;
// To store the graph as an adjacency list
vector<int> edgesArray[200005];
// To store the shortest path
int v_dist[2][200000];
void performBFS(int *v_dist, int start) {
int que[200000];
// Initialize all que[] elements with maxi
fill(v_dist, v_dist + N, maxi);
int q_right = 0, q_left = 0;
que[q_right++] = start;
v_dist[start] = 0;
// BFS algorithm
while (q_left < q_right) {
int temp = que[q_left++];
// Iteraet the current edge
for (int ed : edgesArray[temp]) {
// For non-visited vertice
if (v_dist[ed] == maxi) {
// Change the distance
v_dist[ed] = v_dist[temp] + 1;
// Add to the queue
que[q_right++] = ed;
}
}
}
}
void getShortestPath(int s_edges[], int K) {
vector<pair<int, int>> distDiff;
// Updating the shortest distance between 0 to other nodes
performBFS(v_dist[0], 0);
// Updating distance between last node and other nodes
performBFS(v_dist[1], N - 1);
for (int p = 0; p < K; p++) {
// Get minimum distance for each s_edges node
distDiff.emplace_back(v_dist[0][s_edges[p]] - v_dist[1][s_edges[p]], s_edges[p]);
}
// Sort distances
sort(distDiff.begin(), distDiff.end());
int shortDist = 0;
int maximumDist = -maxi;
// Traverse distDiff[]
for (auto iter : distDiff) {
int current = iter.second;
// maximumDist is a distance from 0 to a. We add distance from a to N - 1 node and take the shortest distance.
shortDist = max(shortDist, maximumDist + v_dist[1][current]);
// Maximizing the difference
maximumDist = max(maximumDist, v_dist[0][current]);
}
cout << "The minimum path cost after adding an edge between selected nodes is - " << min(v_dist[0][N - 1], shortDist + 1);
}
int main() {
// Total nodes and edges
N = 6, M = 5;
// selected vertices
int K = 2;
int s_edges[] = {1, 4};
// Sort array of selected vertices
sort(s_edges, s_edges + K);
// Creating the graph
edgesArray[0].push_back(1);
edgesArray[1].push_back(0);
edgesArray[1].push_back(2);
edgesArray[2].push_back(1);
edgesArray[2].push_back(3);
edgesArray[3].push_back(2);
edgesArray[3].push_back(4);
edgesArray[4].push_back(3);
edgesArray[4].push_back(5);
edgesArray[5].push_back(4);
getShortestPath(s_edges, K);
return 0;
}
輸出
The minimum path cost after adding an edge between selected nodes is - 3
時間複雜度 - O(K*logK + N)，其中 O(KlogK) 用於對 'distDiff' 列表進行排序，O(N) 用於執行 BFS 遍歷。
空間複雜度 - O(K + N)，其中 O(K) 用於對列表進行排序，O(N) 用於 BFS 遍歷中使用的 que[] 陣列。
問題的邏輯部分是獲取每個節點到源節點和目標節點的距離，根據其距離差對選定頂點進行排序，並在兩個相鄰頂點之間新增一條邊以最大化最短路徑。
146 次檢視
