Del 1 al K de las longitudes de ruta más cortas desde el Node 1 al N en el gráfico dado

Dado un gráfico dirigido y ponderado de N Nodes y M aristas, la tarea es encontrar las longitudes de ruta más cortas de la 1 a la K desde el Node ¹ hasta el N.

Ejemplos:

Entrada: N = 4, M = 6, K = 3, aristas = {{1, 2, 1}, {1, 3, 3}, {2, 3, 2}, {2, 4, 6}, { 3, 2, 8}, {3, 4, 1}}
Salida: 4 4 7
Explicación: La longitud de ruta más corta de 1 a N es 4, la segunda longitud más corta también es 4 y la tercera longitud más corta es 7.

Entrada: N = 3, M = 3, K = 2, bordes = {{1, 2, 2}, {2, 3, 2}, {1, 3, 1}}
Salida: 1 4

Enfoque: la idea es atravesar todos los vértices del gráfico usando BFS y usar la cola de prioridad para almacenar los vértices para los que aún no se ha finalizado la distancia más corta, y también para obtener el vértice de distancia mínima . Siga los pasos a continuación para el enfoque. 

• Inicialice una cola de prioridad , digamos, pq de tamaño N para almacenar el número de vértice y el valor de distancia.
• Inicialice un vector 2-d , digamos, dis de tamaño N*K e inicialice todos los valores con un número muy grande, digamos, 1e9.
• Establezca dis[1][0] en cero, el valor de distancia del vértice de origen.
• Iterar mientras pq no está vacío.
  • Extraiga el valor de pq y almacene el valor del vértice en la variable u y la distancia del vértice en la variable d.
  • Si d es mayor que la distancia u , entonces continúa.
  • Para cada vértice adyacente v de u , verifique si el valor de distancia Kth es mayor que el peso de uv más el valor de distancia de u, luego actualice el valor de distancia Kth de v y ordene las distancias k del vértice v.

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

// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find K shortest path lengths
void findKShortest(int edges[][3], int n, int m, int k)
{
 
    // Initialize graph
    vector<vector<pair<int, int> > > g(n + 1);
    for (int i = 0; i < m; i++) {
        // Storing edges
        g[edges[i][0]].push_back({ edges[i][1], edges[i][2] });
    }
 
    // Vector to store distances
    vector<vector<int> > dis(n + 1, vector<int>(k, 1e9));
 
    // Initialization of priority queue
    priority_queue<pair<int, int>,
                   vector<pair<int, int> >,
                   greater<pair<int, int> > >
        pq;
    pq.push({ 0, 1 });
    dis[1][0] = 0;
 
    // while pq has elements
    while (!pq.empty()) {
        // Storing the node value
        int u = pq.top().second;
 
        // Storing the distance value
        int d = (pq.top().first);
        pq.pop();
        if (dis[u][k - 1] < d)
            continue;
        vector<pair<int, int> > v = g[u];
 
        // Traversing the adjacency list
        for (int i = 0; i < v.size(); i++) {
            int dest = v[i].first;
            int cost = v[i].second;
 
            // Checking for the cost
            if (d + cost < dis[dest][k - 1]) {
                dis[dest][k - 1] = d + cost;
 
                // Sorting the distances
                sort(dis[dest].begin(), dis[dest].end());
 
                // Pushing elements to priority queue
                pq.push({ (d + cost), dest });
            }
        }
    }
 
    // Printing K shortest paths
    for (int i = 0; i < k; i++) {
        cout << dis[n][i] << " ";
    }
}
 
// Driver Code
int main()
{
 
    // Given Input
    int N = 4, M = 6, K = 3;
    int edges[][3] = { { 1, 2, 1 }, { 1, 3, 3 },
                       { 2, 3, 2 }, { 2, 4, 6 },
                       { 3, 2, 8 }, { 3, 4, 1 } };
 
    // Function Call
    findKShortest(edges, N, M, K);
 
    return 0;
}

<script>
 
// Javascript implementation of above approach
 
// Function to find K shortest path lengths
function findKShortest(edges, n, m, k)
{
 
    // Initialize graph
    var g = Array.from(Array(n + 1), ()=>new Array());
    for (var i = 0; i < m; i++)
    {
     
        // Storing edges
        g[edges[i][0]].push([edges[i][1], edges[i][2]]);
    }
 
    // Vector to store distances
    var dis = Array.from(Array(n+1), ()=> Array(k).fill(1000000000));
 
    // Initialization of priority queue
    var pq = [];
    pq.push([0, 1]);
    dis[1][0] = 0;
 
    // while pq has elements
    while (pq.length != 0)
    {
     
        // Storing the node value
        var u = pq[pq.length-1][1];
 
        // Storing the distance value
        var d = (pq[pq.length-1][0]);
        pq.pop();
        if (dis[u][k - 1] < d)
            continue;
        var v = g[u];
 
        // Traversing the adjacency list
        for (var i = 0; i < v.length; i++) {
            var dest = v[i][0];
            var cost = v[i][1];
 
            // Checking for the cost
            if (d + cost < dis[dest][k - 1]) {
                dis[dest][k - 1] = d + cost;
 
                // Sorting the distances
                dis[dest].sort((a,b)=>a-b);
 
                // Pushing elements to priority queue
                pq.push([(d + cost), dest ]);
                pq.sort();
            }
        }
    }
 
    // Printing K shortest paths
    for (var i = 0; i < k; i++) {
        document.write(dis[n][i] + " ");
    }
}
 
// Driver Code
 
// Given Input
var N = 4, M = 6, K = 3;
var edges = [ [ 1, 2, 1 ], [ 1, 3, 3 ],
                   [ 2, 3, 2 ], [ 2, 4, 6 ],
                   [ 3, 2, 8 ], [ 3, 4, 1 ] ];
                    
// Function Call
findKShortest(edges, N, M, K);
 
// This code is contributed by rrrtnx.
</script>

4 4 7 

Complejidad temporal: O((N+M)*KlogK)
Espacio auxiliar: O(NK)