Dado un grafo no dirigido G , la tarea es encontrar el camino más corto de longitud par, dado 1 como Node de origen y N como Node de destino. La longitud de la ruta se refiere al número de aristas presentes en una ruta (no al costo de la ruta).
Ejemplos:
Entrada: N = 5, G se da a continuación:
Salida: 10
Explicación:
Todas las rutas desde 1 (Node de origen) hasta 5 (Node de destino) son:
1->2->5
Costo: 16 Longitud: 2 (par)
1->2->3->5
Costo: 4 Longitud: 3(impar)
1->2->3->4->5
Costo: 10 Longitud: 4(par)
El camino más corto es 1->2->3->5 con costo total 4, pero tiene un camino de longitud impar y dado que solo nos interesan los caminos de longitud par, el camino más corto con longitud par es 1->2->3->4->5, con un costo total de 10.Entrada 2: N = 4, G se da a continuación:
Salida: -1
Explicación:
No hay una ruta de longitud uniforme desde 1 (Node de origen) a 4 (Node de destino).
Enfoque:
Cree un nuevo gráfico ( G’ ). Para cada Node V en el gráfico inicial G , cree dos nuevos Nodes V_par y V_odd .
Aquí, V_impar se representará como ((V * 10) + 1) y V_par como ((V * 10) + 2).
Por ejemplo, si el Node V = 4, entonces V_impar = 41 y V_par = 42.
Ahora, para cada arista ( U, V ) en G , agregue dos nuevas aristas en G’ , (U_par, V_odd) y (U_odd, V_par) . Finalmente, encuentre la ruta más corta desde el Node (source_even) hasta el Node (destination_even) utilizando el algoritmo de ruta más corta de Dijkstra .
Para el Gráfico dado en la Entrada 1 (arriba), G’ se puede representar como:
Se puede observar en el gráfico G’ que solo hay caminos de longitud par desde (1_par) a (5_par) . Por lo tanto, los caminos de longitud impar se separan en G’ y se puede obtener el camino más corto requerido.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; const int MAXX = 10000, INF = 1e9; // Adjacency List: to represent graph vector<vector<pair<int, int> > > adj(MAXX * 10 + 3); // Distance Array: to store shortest // distance to every node vector<int> dist(MAXX * 10 + 3, INF); // returns value which will // represent even_x int even(int x) { return x * 10 + 2; } // returns value which will // represent odd_x int odd(int x) { return x * 10 + 1; } // converting edge (a->b) to 2 // different edges i.e. (a->b) // converts to (1). even_a -> odd_b // (2). odd_a -> even_b // since, graph is undirected, so we // push them in reverse order too // hence, 4 push_back operations are // there. void addEdge(int a, int b, int cost) { adj[even(a)].push_back( { odd(b), cost }); adj[odd(a)].push_back( { even(b), cost }); adj[odd(b)].push_back( { even(a), cost }); adj[even(b)].push_back( { odd(a), cost }); } // Function calculates shortest // distance to all nodes from // "source" using Dijkstra // Shortest Path Algorithm // and returns shortest distance // to "destination" int dijkstra(int source, int destination) { /* Priority Queue/min-heap to store and process (distance, node) */ priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq; // pushing source node to // priority queue and dist from // source to source is set to 0 pq.push({ 0, even(source) }); dist[even(source)] = 0; while (!pq.empty()) { // U is the node at top // of the priority queue // note that pq.top().first // refers to the Distance // and pq.top().second // will refer to the Node int u = pq.top().second; pq.pop(); // exploring all neighbours // of node u for (pair<int, int> p : adj[u]) { /* v is neighbour node of u and c is the cost/weight of edge (u, v) */ int v = p.first; int c = p.second; // relaxation: checking if there // is a shorter path to v via u if (dist[u] + c < dist[v]) { // updating distance of v dist[v] = dist[u] + c; pq.push({ dist[v], v }); } } } // returning shortest // distance to "destination" return dist[even(destination)]; } // Driver function int main() { // n = number of Nodes, // m = number of Edges int n = 5, m = 6; addEdge(1, 2, 1); addEdge(2, 3, 2); addEdge(2, 5, 15); addEdge(3, 5, 1); addEdge(3, 4, 4); addEdge(5, 4, 3); int source = 1; int destination = n; int ans = dijkstra(source, destination); // if ans is INF: There is no // even length path from source // to destination else path // exists and we print the // shortest distance if (ans == INF) cout << "-1" << "\n"; else cout << ans << "\n"; return 0; }
Java
// Java program for the above approach import java.util.ArrayList; import java.util.Arrays; import java.util.PriorityQueue; class GFG{ static class Pair implements Comparable<Pair> { int first, second; public Pair(int first, int second) { this.first = first; this.second = second; } @Override public int compareTo(GFG.Pair o) { if (this.first == o.first) { return this.second - o.second; } return this.first - o.first; } } static final int MAXX = 10000, INF = (int)1e9; // Adjacency List: to represent graph @SuppressWarnings("unchecked") static ArrayList<Pair>[] adj = new ArrayList[MAXX * 10 + 3]; // Distance Array: to store shortest // distance to every node static int[] dist = new int[MAXX * 10 + 3]; // Returns value which will // represent even_x static int even(int x) { return x * 10 + 2; } // Returns value which will // represent odd_x static int odd(int x) { return x * 10 + 1; } // Converting edge (a->b) to 2 // different edges i.e. (a->b) // converts to (1). even_a -> odd_b // (2). odd_a -> even_b // since, graph is undirected, so we // push them in reverse order too // hence, 4 push_back operations are // there. static void addEdge(int a, int b, int cost) { adj[even(a)].add(new Pair(odd(b), cost)); adj[odd(a)].add(new Pair(even(b), cost)); adj[odd(b)].add(new Pair(even(a), cost)); adj[even(b)].add(new Pair(odd(a), cost)); } // Function calculates shortest // distance to all nodes from // "source" using Dijkstra // Shortest Path Algorithm // and returns shortest distance // to "destination" static int dijkstra(int source, int destination) { // Priority Queue/min-heap to store // and process (distance, node) PriorityQueue<Pair> pq = new PriorityQueue<>(); // Pushing source node to // priority queue and dist from // source to source is set to 0 pq.add(new Pair(0, even(source))); dist[even(source)] = 0; while (!pq.isEmpty()) { // U is the node at top // of the priority queue // note that pq.top().first // refers to the Distance // and pq.top().second // will refer to the Node int u = pq.poll().second; // Exploring all neighbours // of node u for(Pair p : adj[u]) { // v is neighbour node of u and // c is the cost/weight of edge (u, v) int v = p.first; int c = p.second; // Relaxation: checking if there // is a shorter path to v via u if (dist[u] + c < dist[v]) { // Updating distance of v dist[v] = dist[u] + c; pq.add(new Pair(dist[v], v)); } } } // Returning shortest // distance to "destination" return dist[even(destination)]; } // Driver code public static void main(String[] args) { for(int i = 0; i < MAXX * 10 + 3; i++) { adj[i] = new ArrayList<Pair>(); } Arrays.fill(dist, INF); // n = number of Nodes, // m = number of Edges int n = 5, m = 6; addEdge(1, 2, 1); addEdge(2, 3, 2); addEdge(2, 5, 15); addEdge(3, 5, 1); addEdge(3, 4, 4); addEdge(5, 4, 3); int source = 1; int destination = n; int ans = dijkstra(source, destination); // If ans is INF: There is no // even length path from source // to destination else path // exists and we print the // shortest distance if (ans == INF) System.out.println("-1"); else System.out.println(ans); } } // This code is contributed by sanjeev2552
Python3
# Python3 program for the above approach import heapq as hq MAXX = 10000 INF = 1e9 # Adjacency List: to represent graph adj = [[] for _ in range(MAXX * 10 + 3)] # Distance Array: to store shortest # distance to every node dist = [INF] * (MAXX * 10 + 3) # returns value which will # represent even_x def even(x): return x * 10 + 2 # returns value which will # represent odd_x def odd(x): return x * 10 + 1 # converting edge (a->b) to 2 # different edges i.e. (a->b) # converts to (1). even_a -> odd_b # (2). odd_a -> even_b # since, graph is undirected, so we # push them in reverse order too # hence, 4 append operations are # there. def addEdge(a, b, cost): adj[even(a)].append((odd(b), cost)) adj[odd(a)].append((even(b), cost)) adj[odd(b)].append((even(a), cost)) adj[even(b)].append((odd(a), cost)) # Function calculates shortest # distance to all nodes from # "source" using Dijkstra # Shortest Path Algorithm # and returns shortest distance # to "destination" def dijkstra(source, destination): # Priority Queue/min-heap # to store and process # (distance, node) pq = [] # pushing source node to # priority queue and dist from # source to source is set to 0 hq.heappush(pq, (0, even(source))) dist[even(source)] = 0 while pq: # U is the node at top # of the priority queue # note that pq.top()[1] # refers to the Distance # and pq.top()[1] # will refer to the Node u = hq.heappop(pq)[1] # exploring all neighbours # of node u # v is neighbour node of u # and c is the cost/weight # of edge (u, v) for v, c in adj[u]: # relaxation: checking if there # is a shorter path to v via u if dist[u] + c < dist[v]: # updating distance of v dist[v] = dist[u] + c hq.heappush(pq, (dist[v], v)) # returning shortest # distance to "destination" return dist[even(destination)] # Driver function if __name__ == "__main__": # n = number of Nodes, # m = number of Edges n = 5 m = 6 addEdge(1, 2, 1) addEdge(2, 3, 2) addEdge(2, 5, 15) addEdge(3, 5, 1) addEdge(3, 4, 4) addEdge(5, 4, 3) source = 1 destination = n ans = dijkstra(source, destination) # if ans is INF: There is no # even length path from source # to destination else path # exists and we print # shortest distance if ans == INF: print(-1) else: print(ans)
10
Complejidad de Tiempo: (E * log(V))
Espacio Auxiliar: O(V + E)