Dado un gráfico no dirigido ponderado que consta de N Nodes y M aristas, la tarea es encontrar la distancia más corta entre dos Nodes A y B reduciendo el peso de una arista a la mitad.
Ejemplos:
Entrada: A = 0, B = 2, a continuación se muestra el gráfico
Salida: 8
Explicación:
Después de reducir el peso de la arista que conecta 1 y 2 a la mitad, modifica su nuevo peso a 4. Ahora, la distancia más corta para llegar a 2 desde 0 a través del camino 0 -> 1 -> 2 es (4 + 4 ) = 8.
Por lo tanto, imprima 8.
Enfoque: el problema dado se puede resolver manteniendo dos arrays, la array de distancia más corta tomando el Node fuente como A , que almacenará la distancia más corta de todos los Nodes desde A , y de manera similar , la array de distancia más corta tomando el Node fuente como B. Estas arrays se pueden calcular utilizando el algoritmo de Dijkstra . Siga los pasos a continuación para resolver el problema anterior:
- Use el algoritmo de Dijkstra para almacenar la distancia más corta de cada Node desde A en una array disA[] .
- Use el algoritmo de Dijkstra para almacenar la distancia más corta de cada Node desde B en una array disB[] .
- Supongamos que la arista i = {u i , v i , wt i } es decir, la arista i conecta el Node u i con v i y tiene un peso de wt i .
- Ahora, itere sobre todos los bordes y para cada borde realice un seguimiento de la función como:
f(borde i ) = min( disA[u i ] + disB[v i ], disA[v i ] + disB[u i ]) + (wt i /2) .
- La relación anterior da el valor mínimo de f(borde) , que es la distancia más corta resultante.
A continuación se muestra la implementación del enfoque anterior:
C++14
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Stores the input Graph
vector<pair<int, int> > graph[100001];
// Stores edges of input Graph
vector<vector<int> > edges;
// Function to input Edges
void add_edge(int u, int v, int w)
{
graph[u].push_back({ v, w });
graph[v].push_back({ u, w });
edges.push_back({ u, v, w });
}
// Function to find the shortest distance
// to each node from the src node using
// Dijkstra’s Algorithm
vector<int> dijsktras(int src, int N)
{
// Stores the shortest distance of
// each node form src node
vector<int> dis(N, INT_MAX);
vector<bool> vis(N, false);
// Stores the node and current
// minimum distance in a heap
priority_queue<pair<int, int>,
vector<pair<int, int> >,
greater<pair<int, int> > >
pq;
pq.push({ 0, src });
dis[src] = 0;
// BFS for single source shortest
// path algorithm
while (!pq.empty()) {
// Top of the PQ
auto cur = pq.top();
pq.pop();
// Store the node and weight
int node = cur.second;
int weight = cur.first;
// If node is already visited
if (vis[node])
continue;
vis[node] = true;
// Traverse the adjacency list
// of the node
for (auto child : graph[node]) {
// If the distance obtained
// from parent is less than
// the current minimum
// distance stored for child
if (dis[child.first]
> child.second + weight) {
dis[child.first] = weight
+ child.second;
// Push the next pair
// in the PQ
pq.push({ dis[child.first],
child.first });
}
}
}
// Return the maximum distance
return dis;
}
// Function to find shortest distance
// between two nodes by reducing any
// one weight of an edge by half
int shortestDistance(int N, int M,
int A, int B)
{
// Stores the shortest distance
// of each node from A
vector<int> disA = dijsktras(A, N);
// Stores the shortest distance
// of each node from B
vector<int> disB = dijsktras(B, N);
int ans = disA[B];
for (auto edge : edges) {
int u = edge[0], v = edge[1];
int weight = edge[2];
// Calculate the value of f(edge)
// for the current edge
int cur = min(disA[u] + disB[v],
disA[v] + disB[u])
+ (weight / 2);
// Keep track of the minimum of
// f(edge) for all edges
ans = min(ans, cur);
}
// Return Answer
return ans;
}
// Driver Code
int main()
{
int N = 9, M = 14, A = 0, B = 2;
// Create a Graph
add_edge(0, 1, 4);
add_edge(1, 2, 8);
add_edge(2, 3, 7);
add_edge(3, 4, 9);
add_edge(4, 5, 10);
add_edge(5, 6, 2);
add_edge(6, 7, 1);
add_edge(7, 0, 8);
add_edge(1, 7, 11);
add_edge(7, 8, 7);
add_edge(2, 8, 2);
add_edge(6, 8, 6);
add_edge(2, 5, 4);
add_edge(3, 5, 14);
// Function Call
cout << shortestDistance(N, M, A, B);
return 0;
}
8
Complejidad de tiempo: O(M*log N)
Espacio auxiliar: O(N + M)
Publicación traducida automáticamente
Artículo escrito por sanyamsharma1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA