数据结构
网络
关系数据库管理系统(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
