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