資料結構
網路
關係資料庫管理系統(RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學修改邊權重的Dijkstra演算法最小成本
在這個問題中，我們需要使用Dijkstra演算法找到從1到N的最小路徑，並且我們可以將任何一條邊的權重更新為cost/2。
在這裡，我們將找到每個節點從源節點到目標節點的距離。之後，我們將取從源節點到節點u的最短距離和從目標節點到節點v的最短距離，並將它們與u->v邊的權重的一半相加。透過這種方式，我們將找到從1到N的最小路徑成本。
問題陳述 - 我們得到了一個以元組形式表示的無向圖。元組{p, q, r}表示p和q之間權重為r的邊。我們需要使用Dijkstra演算法找到從1到N的最小路徑成本。還給定我們可以執行一次操作，將任何一條邊的權重更新為cost/2。
示例
輸入
[{1, {2, 7}}, {1, {3, 4}}, {1, {4, 8}}, {3, {4, 4}}, {4, {5, 3}}]
輸出
7
解釋 - 這是給定的圖。
1
/ | \
2 3 - 4 - 5
在這裡，我們需要從1到達5。所以存在兩條路徑。一條是1->3->4->5，另一條是1->4->5。兩條路徑的成本都是11。如果我們選擇第二條路徑並將1->4的成本從8減少到4，則路徑成本為7。
輸入
[{1, {2, 3}}, {2, {1, 6}}, {2, {3, 2}}]
輸出
3
解釋 - 我們在1到2之間有兩條邊。因此，我們可以考慮權重為3的邊，將其值更新為3/2，等於1。因此，從1到3的路徑成本只有3。
方法
在這種方法中，我們將使用Dijkstra演算法找到每個節點從源節點和目標節點的距離。之後，對於連線兩個頂點的每條邊，我們將取起始節點到源節點的距離、權重的一半和結束節點到目標節點的距離，並將它們相加。同時，我們將跟蹤從1到N的最小路徑成本。
演算法
步驟1 - 定義一個列表來儲存圖。
步驟2 - 遍歷每個給定的邊，並執行以下步驟。
步驟2.1 - 從當前元組中獲取源節點、目標節點和權重。
步驟2.2 - 在列表的源節點索引處插入{目標節點，權重}對，並在列表的目標節點索引處插入{源節點，權重}對。
步驟3 - 此外，定義source_dist和dest_dist列表分別儲存每個節點到源節點和目標節點的距離。
步驟4 - 呼叫executeDijkstra()函式兩次，分別查詢每個節點到起始節點和結束節點的距離。
步驟4.1 - 在executeDijkstra()函式中，根據節點總數調整'dist'列表的大小，並將dist[source]更新為0。
步驟4.2 - 定義優先佇列，並使用greater<pair<int, int>>比較器函式來使用最小堆優先佇列。優先佇列將用於儲存當前節點到源節點的距離和節點值。
步驟4.3 - 將源節點插入佇列。
步驟4.4 - 遍歷佇列，直到佇列為空。在迴圈中，從佇列中獲取第一個元素並遍歷其邊。
步驟4.5 - 遍歷邊時，獲取邊的終點節點和權重。
步驟4.6 - 如果到起始節點的距離 + 邊的權重小於到結束節點的距離，則更新結束節點的距離。同時，將更新後的對插入佇列。
步驟5 - 定義'minCost'變數並將其初始化為從1到N的距離。
步驟6 - 開始遍歷所有邊。將起始節點到源節點的距離、權重的一半和結束節點到目標節點的距離相加。如果結果值大於minCost，則更新它。
步驟7 - 返回minCost值。
示例
#include <bits/stdc++.h>
using namespace std;
#define INF 1e9
void executeDijkstra(int source, int nodes, vector<pair<int, int>> list[], vector<int> &dist) {
// Resizing
dist.resize(nodes, INF);
// Initialize source node with 0.
dist[source] = 0;
// To store edges cost
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> p_que;
// Insert distance and source node
p_que.push({dist[source], source});
while (!p_que.empty()) {
// Get the first node from the queue
int start = p_que.top().second;
// Pop the top node
p_que.pop();
// Traverse all connected nodes to the current node
for (auto &ed : list[start]) {
// Get the start and end node of the edge
int end = ed.first;
int cost = ed.second;
// Updating the distance to minimum
if (dist[start] + cost < dist[end]) {
dist[end] = dist[start] + cost;
p_que.push({dist[end], end});
}
}
}
}
void getMinimumCost(vector<pair<int, pair<int, int>>> &edges, int nodes, int totalEdges) {
vector<pair<int, int>> list[100005];
// Traverse edges
for (int p = 0; p < totalEdges; p++) {
// Add graph parameters to list
int source = edges[p].first;
int destination = edges[p].second.first;
int cost = edges[p].second.second;
list[source].push_back({destination, cost});
list[destination].push_back({source, cost});
}
// To store the distance of 1 to P and N to P
vector<int> source_dist;
vector<int> dest_dist;
// For each vertex, find the path cost from the source node
executeDijkstra(1, nodes + 1, list, source_dist);
// For each vertex, find the path cost from the destination node
executeDijkstra(nodes, nodes + 1, list, dest_dist);
// To store minimum path cost
int minCost = source_dist[nodes];
for (auto &ed : edges) {
// Get the edges
int source = ed.first;
int destination = ed.second.first;
int cost = ed.second.second;
// Cost for 1 to N = (1 to P) + (p to p + 1) + (P + 1 to N)
int cur_cost = source_dist[source] + cost / 2 + dest_dist[destination];
minCost = min(minCost, cur_cost);
}
cout << "The minimum cost for 1 to N after modifying any single edge is " << minCost << '\n';
}
int main() {
int nodes = 5;
int totalEdges = 5;
vector<pair<int, pair<int, int>>> edges;
edges.push_back({1, {2, 7}});
edges.push_back({1, {3, 4}});
edges.push_back({1, {4, 8}});
edges.push_back({3, {4, 4}});
edges.push_back({4, {5, 3}});
getMinimumCost(edges, nodes, totalEdges);
return 0;
}
輸出
The minimum cost for 1 to N after modifying any single edge is 7
時間複雜度 - O(MlogN)
空間複雜度 - O(N)
在這裡，我們只用cost/2替換了一條邊的權重。但是，程式設計師可以嘗試編寫程式碼來替換K條邊的權重以進行更多練習。
瀏覽量：259
