C++ 添加一条边以最大化给定顶点之间的最短路径

在这个问题中，我们将通过添加两个选定顶点之间的边来最大化从顶点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 − 两次执行preformBFS()函数，分别找到每个节点与源节点和目标节点之间的距离。

步骤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更新，并将其插入到q_right索引处的que []数组中。然后，将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[]数组的空间复杂度。

问题的逻辑部分是计算每个节点与源节点和目标节点之间的距离，根据它们的距离差对选定的顶点进行排序，并在相邻的顶点之间添加一条边以最大化最短路径。