Dado un gráfico ponderado dirigido y el vértice de origen y destino . La tarea es encontrar la suma de la distancia más corta en el camino que va desde el origen hasta el destino y luego desde el destino hasta el origen , de modo que ambos caminos tengan al menos un vértice común que no sea el origen y el destino.
Nota : Al pasar del destino al origen, todas las direcciones de los bordes se invierten.
Ejemplos:
Entrada: src = 0, des = 1
Salida: 17
Explicación:
el vértice común es 4 y la ruta es 0 -> 4 -> 3 -> 1 -> 4 -> 0
Enfoque: La idea es utilizar el algoritmo de Dijkstra . Al encontrar el camino más corto desde el origen hasta el destino y el camino más corto desde el destino hasta el origen utilizando el algoritmo de Dijkstra, es posible que no resulte en un camino donde haya al menos un Node en común, excepto el vértice de origen y el de destino.
- Sea s el vértice de origen y d el vértice de destino y v el Node intermedio común en los caminos de origen a destino y de destino a origen. El par de caminos más cortos, de modo que v esté en la intersección de estos dos caminos, es un camino: s -> v -> d -> v -> s y su longitud es
dis[s][v] + dis[v][d] + dis[d][v] + dis[v][s]
- Dado que s y d son fijos, simplemente encuentre v tal que proporcione el camino más corto.
- Para encontrar tal v , siga los pasos a continuación:
- Encuentre la distancia más corta desde todos los vértices hasta s y d , lo que nos da los valores de dis[v][s] y dis[v][d] . Para encontrar la ruta más corta desde todos los vértices hasta un Node determinado, consulte Rutas más cortas desde todos los vértices hasta un destino .
- Encuentre la distancia más corta de todos los vértices desde s y d , lo que nos da d[s][v] y d[d][v] .
- Iterar para todos los v y encontrar el mínimo de d[s][v] + d[v][d] + d[d][v] + d[v][s] .
A continuación se muestra la implementación del enfoque anterior:
CPP
// CPP implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
// iPair represents the Integer Pair
typedef pair<int, int> iPair;
// This class represents
// a directed graph using
// adjacency list representation
class Graph {
// Number of vertices
int V;
// In a weighted graph, store vertex
// and weight pair for every edge
list<pair<int, int> >* adj;
public:
// Constructor
Graph(int V);
// Function to add an edge to graph
void addEdge(int u, int v, int w);
// Find shortest path from
// source vertex to all vertex
void shortestPath(int src,
vector<int>& dist);
};
// Allocates memory for adjacency list
Graph::Graph(int V)
{
this->V = V;
adj = new list<iPair>[V];
}
// Function to add an edge to the graph
void Graph::addEdge(int u, int v, int w)
{
adj[v].push_back(make_pair(u, w));
}
// Function to find the shortest paths
// from source to all other vertices
void Graph::shortestPath(int src,
vector<int>& dist)
{
// Create a priority queue to
// store vertices that
// are being preprocessed
priority_queue<iPair,
vector<iPair>,
greater<iPair> >
pq;
// Insert source itself in priority
// queue and initialize
// its distance as 0
pq.push(make_pair(0, src));
dist[src] = 0;
// Loop till priority queue
// becomes empty (or all
// distances are not finalized)
while (!pq.empty()) {
// The first vertex in pair
// is the minimum distance
// vertex, extract it from
// priority queue
int u = pq.top().second;
pq.pop();
// 'i' is used to get all
// adjacent vertices of a vertex
list<pair<int, int> >::iterator i;
for (i = adj[u].begin(); i != adj[u].end(); ++i) {
// Get vertex label and
// weight of current
// adjacent of u
int v = (*i).first;
int weight = (*i).second;
// If there is shorted
// path to v through u
if (dist[v] > dist[u] + weight) {
// Updating distance of v
dist[v] = dist[u] + weight;
pq.push(make_pair(dist[v], v));
}
}
}
}
// Function to return the
// required minimum path
int minPath(int V, int src, int des,
Graph g, Graph r)
{
// Create a vector for
// distances and
// initialize all distances
// as infinite (INF)
// To store distance of all
// vertex from source
vector<int> dist(V, INF);
// To store distance of all
// vertex from destination
vector<int> dist2(V, INF);
// To store distance of source
// from all vertex
vector<int> dist3(V, INF);
// To store distance of
// destination from all vertex
vector<int> dist4(V, INF);
// Computing shortest path from
// source vertex to all vertices
g.shortestPath(src, dist);
// Computing shortest path from
// destination vertex to all vertices
g.shortestPath(des, dist2);
// Computing shortest path from
// all the vertices to source
r.shortestPath(src, dist3);
// Computing shortest path from
// all the vertices to destination
r.shortestPath(des, dist4);
// Finding the intermediate node (IN)
// such that the distance of path
// src -> IN -> des -> IN -> src is minimum
// To store the shortest distance
int ans = INT_MAX;
for (int i = 0; i < V; i++) {
// Intermediate node should not be
// the source and destination
if (i != des && i != src)
ans = min(
ans,
dist[i] + dist2[i]
+ dist3[i] + dist4[i]);
}
// Return the minimum path required
return ans;
}
// Driver code
int main()
{
// Create the graph
int V = 5;
int src = 0, des = 1;
// To store the original graph
Graph g(V);
// To store the reverse graph
// and compute distance from all
// vertex to a particular vertex
Graph r(V);
// Adding edges
g.addEdge(0, 2, 1);
g.addEdge(0, 4, 5);
g.addEdge(1, 4, 1);
g.addEdge(2, 0, 10);
g.addEdge(2, 3, 5);
g.addEdge(3, 1, 1);
g.addEdge(4, 0, 5);
g.addEdge(4, 2, 100);
g.addEdge(4, 3, 5);
// Adding edges in reverse direction
r.addEdge(2, 0, 1);
r.addEdge(4, 0, 5);
r.addEdge(4, 1, 1);
r.addEdge(0, 2, 10);
r.addEdge(3, 2, 5);
r.addEdge(1, 3, 1);
r.addEdge(0, 4, 5);
r.addEdge(2, 4, 100);
r.addEdge(3, 4, 5);
cout << minPath(V, src, des, g, r);
return 0;
}
Python3
# Python implementation of the approach from typing import List from queue import PriorityQueue from sys import maxsize as INT_MAX INF = 0x3f3f3f3f # This class represents # a directed graph using # adjacency list representation class Graph: def __init__(self, V: int) -> None: # Number of vertices self.V = V # In a weighted graph, store vertex # and weight pair for every edge self.adj = [[] for _ in range(V)] # Function to add an edge to the graph def addEdge(self, u: int, v: int, w: int) -> None: self.adj[v].append((u, w)) # Function to find the shortest paths # from source to all other vertices def shortestPath(self, src: int, dist: List[int]) -> None: # Create a priority queue to # store vertices that # are being preprocessed pq = PriorityQueue() # Insert source itself in priority # queue and initialize # its distance as 0 pq.put((0, src)) dist[src] = 0 # Loop till priority queue # becomes empty (or all # distances are not finalized) while not pq.empty(): # The first vertex in pair # is the minimum distance # vertex, extract it from # priority queue u = pq.get()[1] # 'i' is used to get all # adjacent vertices of a vertex for i in self.adj[u]: # Get vertex label and # weight of current # adjacent of u v = i[0] weight = i[1] # If there is shorted # path to v through u if dist[v] > dist[u] + weight: # Updating distance of v dist[v] = dist[u] + weight pq.put((dist[v], v)) # Function to return the # required minimum path def minPath(V: int, src: int, des: int, g: Graph, r: Graph) -> int: # Create a vector for # distances and # initialize all distances # as infinite (INF) # To store distance of all # vertex from source dist = [INF for _ in range(V)] # To store distance of all # vertex from destination dist2 = [INF for _ in range(V)] # To store distance of source # from all vertex dist3 = [INF for _ in range(V)] # To store distance of # destination from all vertex dist4 = [INF for _ in range(V)] # Computing shortest path from # source vertex to all vertices g.shortestPath(src, dist) # Computing shortest path from # destination vertex to all vertices g.shortestPath(des, dist2) # Computing shortest path from # all the vertices to source r.shortestPath(src, dist3) # Computing shortest path from # all the vertices to destination r.shortestPath(des, dist4) # Finding the intermediate node (IN) # such that the distance of path # src -> IN -> des -> IN -> src is minimum # To store the shortest distance ans = INT_MAX for i in range(V): # Intermediate node should not be # the source and destination if (i != des and i != src): ans = min(ans, dist[i] + dist2[i] + dist3[i] + dist4[i]) # Return the minimum path required return ans # Driver code if __name__ == "__main__": # Create the graph V = 5 src = 0 des = 1 # To store the original graph g = Graph(V) # To store the reverse graph # and compute distance from all # vertex to a particular vertex r = Graph(V) # Adding edges g.addEdge(0, 2, 1) g.addEdge(0, 4, 5) g.addEdge(1, 4, 1) g.addEdge(2, 0, 10) g.addEdge(2, 3, 5) g.addEdge(3, 1, 1) g.addEdge(4, 0, 5) g.addEdge(4, 2, 100) g.addEdge(4, 3, 5) # Adding edges in reverse direction r.addEdge(2, 0, 1) r.addEdge(4, 0, 5) r.addEdge(4, 1, 1) r.addEdge(0, 2, 10) r.addEdge(3, 2, 5) r.addEdge(1, 3, 1) r.addEdge(0, 4, 5) r.addEdge(2, 4, 100) r.addEdge(3, 4, 5) print(minPath(V, src, des, g, r)) # This code is contributed by sanjeev2552
Producción:
17
Publicación traducida automáticamente
Artículo escrito por mysticpeaks y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA