Ruta más corta con un número par de aristas desde el origen hasta el destino

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: 
 

Gráfico de entrada

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: 
 

Gráfico de entrada

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: 
 

Graph G'

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)
Producción: 

10

 

Complejidad de Tiempo: (E * log(V))
Espacio Auxiliar: O(V + E)

Publicación traducida automáticamente

Artículo escrito por SuyashKY y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *