Ruta de costo mínimo desde el Node de origen hasta el Node de destino a través de K Nodes intermedios

Dado un gráfico que consta de N vértices y M aristas ponderadas y una array aristas[][] , en la que cada fila representa los dos vértices conectados por la arista y el peso de la arista, la tarea es encontrar la ruta con la menor suma de pesos desde un vértice de origen dado src hasta un vértice de destino dado dst , formado por K vértices intermedios. Si no existe tal ruta, imprima -1 .

Ejemplos:

Entrada: N = 3, M = 3, src = 0, dst = 2, K = 1, bordes[] = {{0, 1, 100}, {1, 2, 100}, {0, 2, 500} }
Salida: 200
Explicación:  La ruta 0 -> 1 -> 2 es la suma menos ponderada (= 100 + 100 = 200) ruta que conecta src (= 0) y dst (= 2) con exactamente K (= 1) vértice intermedio .

Entrada: N = 3, M = 3, src = 0, dst = 2, K = 0, bordes [] = { { 0, 1, 100 }, { 1, 2, 100 }, { 0, 2, 500 } }
Salida: 500
Explicación:  El borde directo 0 -> 2 con peso 500 es la ruta requerida.

Enfoque: el problema dado se puede resolver utilizando Priority Queue y realizar BFS . Siga los pasos a continuación para resolver este problema:

1. Inicialice una cola de prioridad para almacenar las tuplas {costo para llegar a este vértice, vértice, número de paradas} .
2. Empuje {0, src, k+1} como el primer punto de partida.
3. Muestra el elemento superior de la cola de prioridad . Si todas las paradas están agotadas, repita este paso.
4. Si se alcanza el destino, imprima el costo para llegar al vértice actual.
5. De lo contrario, encuentre el vecino de este vértice que requirió el menor costo para llegar a ese vértice. Póngalo en la cola de prioridad .
6. Repita desde el paso 2 .
7. Si no se encuentra ninguna ruta después de realizar los pasos anteriores, imprima -1 .

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the minimum cost path
// from the source vertex to destination
// vertex via K intermediate vertices
int leastWeightedSumPath(int n,
                         vector<vector<int> >& edges,
                         int src, int dst, int K)
{
    // Initialize the adjacency list
    unordered_map<int,
                  vector<pair<int, int> > >
        graph;
 
    // Generate the adjacency list
    for (vector<int>& edge : edges) {
        graph[edge[0]].push_back(
            make_pair(edge[1], edge[2]));
    }
 
    // Initialize the minimum priority queue
    priority_queue<vector<int>, vector<vector<int> >,
                   greater<vector<int> > >
        pq;
 
    // Stores the minimum cost to
    // travel between vertices via
    // K intermediate nodes
    vector<vector<int> > costs(n,
                               vector<int>(
                                   K + 2, INT_MAX));
 
    costs[src][K + 1] = 0;
 
    // Push the starting vertex,
    // cost to reach and the number
    // of remaining vertices
    pq.push({ 0, src, K + 1 });
 
    while (!pq.empty()) {
        // Pop the top element
        // of the stack
        auto top = pq.top();
 
        pq.pop();
 
        // If destination is reached
        if (top[1] == dst)
 
            // Return the cost
            return top[0];
 
        // If all stops are exhausted
        if (top[2] == 0)
            continue;
 
        // Find the neighbour with minimum cost
        for (auto neighbor : graph[top[1]]) {
 
            // Pruning
            if (costs[neighbor.first][top[2] - 1]
                < neighbor.second + top[0]) {
                continue;
            }
 
            // Update cost
            costs[neighbor.first][top[2] - 1]
                = neighbor.second + top[0];
 
            // Update priority queue
            pq.push({ neighbor.second + top[0],
                      neighbor.first, top[2] - 1 });
        }
    }
 
    // If no path exists
    return -1;
}
 
// Driver Code
int main()
{
    int n = 3, src = 0, dst = 2, k = 1;
    vector<vector<int> > edges
        = { { 0, 1, 100 },
            { 1, 2, 100 },
            { 0, 2, 500 } };
 
    // Function Call to find the path
    // from src to dist via k nodes
    // having least sum of weights
    cout << leastWeightedSumPath(n, edges,
                                 src, dst, k);
 
    return 0;
}

# Python3 program for the above approach
 
# Function to find the minimum cost path
# from the source vertex to destination
# vertex via K intermediate vertices
def leastWeightedSumPath(n, edges, src, dst, K):
    graph = [[] for i in range(3)]
 
    # Generate the adjacency list
    for edge in edges:
        graph[edge[0]].append([edge[1], edge[2]])
 
    # Initialize the minimum priority queue
    pq = []
 
    # Stores the minimum cost to
    # travel between vertices via
    # K intermediate nodes
    costs = [[10**9 for i in range(K + 2)] for i in range(n)]
 
    costs[src][K + 1] = 0
 
    # Push the starting vertex,
    # cost to reach and the number
    # of remaining vertices
    pq.append([ 0, src, K + 1 ])
 
    pq = sorted(pq)[::-1]
 
    while (len(pq) > 0):
       
        # Pop the top element
        # of the stack
        top = pq[-1]
 
        del pq[-1]
 
        # If destination is reached
        if (top[1] == dst):
           
            # Return the cost
            return top[0]
 
        # If all stops are exhausted
        if (top[2] == 0):
            continue
 
        # Find the neighbour with minimum cost
        for neighbor in graph[top[1]]:
 
            # Pruning
            if (costs[neighbor[0]][top[2] - 1] < neighbor[1] + top[0]):
                continue
 
            # Update cost
            costs[neighbor[0]][top[2] - 1] = neighbor[1]+ top[0]
 
            # Update priority queue
            pq.append([neighbor[1]+ top[0],neighbor[0], top[2] - 1])
        pq = sorted(pq)[::-1]
 
    # If no path exists
    return -1
 
# Driver Code
if __name__ == '__main__':
    n, src, dst, k = 3, 0, 2, 1
    edges = [ [ 0, 1, 100 ],
            [ 1, 2, 100 ],
            [ 0, 2, 500 ] ]
 
    # Function Call to find the path
    # from src to dist via k nodes
    # having least sum of weights
    print (leastWeightedSumPath(n, edges, src, dst, k))
 
# This code is contributed by mohit kumar 29.

<script>
// Javascript program for the above approach
 
// Function to find the minimum cost path
// from the source vertex to destination
// vertex via K intermediate vertices
function leastWeightedSumPath(n, edges, src, dst, K)
{
 
    // Initialize the adjacency list
    var graph = new Map();
 
    // Generate the adjacency list
    for (var edge of edges) {
        if(!graph.has(edge[0]))
            graph.set(edge[0], new Array())
        var tmp = graph.get(edge[0]);
        tmp.push([edge[1], edge[2]]);
        graph.set(edge[0],tmp);
    }
 
    // Initialize the minimum priority queue
    var pq = [];
 
    // Stores the minimum cost to
    // travel between vertices via
    // K intermediate nodes
    var costs = Array.from(Array(n+1), ()=>Array(K+2).fill(1000000000));
    costs[src][K + 1] = 0;
 
    // Push the starting vertex,
    // cost to reach and the number
    // of remaining vertices
    pq.push([ 0, src, K + 1 ]);
 
    while (pq.length!=0) {
        // Pop the top element
        // of the stack
        var top = pq[pq.length-1];
 
        pq.pop();
 
        // If destination is reached
        if (top[1] == dst)
 
            // Return the cost
            return top[0];
 
        // If all stops are exhausted
        if (top[2] == 0)
            continue;
 
        if(graph.has(top[1]))
        {
        // Find the neighbour with minimum cost
        for (var neighbor of graph.get(top[1])) {
            
            // Pruning
            if (costs[neighbor[0]][top[2] - 1]
                < neighbor[1] + top[0]) {
                continue;
            }
 
            // Update cost
            costs[neighbor[0]][top[2] - 1]
                = neighbor[1] + top[0];
 
            // Update priority queue
            pq.push([neighbor[1] + top[0],
                      neighbor[0], top[2] - 1 ]);
        }
        }
        pq.sort((a,b)=>{
            if(a[0]==b[0])
             return b[1]-a[1]
            return b[0]-a[0];
        });
    }
 
    // If no path exists
    return -1;
}
 
// Driver Code
var n = 3, src = 0, dst = 2, k = 1;
var edges
    = [ [ 0, 1, 100 ],
        [ 1, 2, 100 ],
        [ 0, 2, 500 ] ];
// Function Call to find the path
// from src to dist via k nodes
// having least sum of weights
document.write(leastWeightedSumPath(n, edges,
                             src, dst, k));
 
// This code is contributed by rrrtnx.
</script>

200

Complejidad de tiempo: O(N * log N) 
Espacio auxiliar : O(N)