Dado un gráfico dirigido y ponderado de N Nodes y M aristas, la tarea es contar el número de caminos de menor longitud entre el Node 1 y N.
Ejemplos:
Entrada: N = 4, M = 5, aristas = {{1, 4, 5}, {1, 2, 4}, {2, 4, 5}, {1, 3, 2}, {3, 4, 3}}
Salida: 2
Explicación: El número de rutas más cortas del Node 1 al Node 4 es 2, con un costo de 5.
Entrada: N = 3, M = 2, bordes = {{1, 2, 4}, {1, 3, 5}}
Salida: 1
Enfoque: El problema se puede resolver mediante el algoritmo de Dijkstra . Use dos arrays, digamos dist[] para almacenar la distancia más corta desde el vértice de origen y paths[] de tamaño N , para almacenar la cantidad de caminos más cortos diferentes desde el vértice de origen hasta el vértice N. Siga estos pasos a continuación para el enfoque.
- Inicialice una cola de prioridad , digamos pq, para almacenar el número de vértice y su valor de distancia.
- Inicialice un vector de ceros, digamos paths[] de tamaño N , y haga que paths[1] sea igual a 1 .
- Inicialice un vector de números grandes (1e9), diga dist[] de tamaño N y haga que dist[1] sea igual a 0 .
- Iterar mientras pq no está vacío.
- Extraiga del pq y almacene el valor del vértice en una variable, digamos u , y el valor de la distancia en la variable d .
- Si d es mayor que u , entonces continúa .
- Para cada v de cada vértice u, si dist[v] > dist[u]+ (costo de borde de u y v), entonces disminuya dist[v] a dist[u] + (costo de borde de u y v) y asigne el número de caminos del vértice u al número de caminos del vértice v .
- Para cada v de cada vértice u, si dist[v] = dist[u] + (costo de borde de u y v) , entonces agregue el número de caminos del vértice u al número de caminos del vértice v .
- Finalmente, imprima rutas [N].
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 INF = 1e9;
const int MAXN = 1e5 + 1;
vector<vector<pair<int, int> > > g(MAXN);
vector<int> dist(MAXN);
vector<int> route(MAXN);
// Function to count number of shortest
// paths from node 1 to node N
void countDistinctShortestPaths(
int n, int m, int edges[][3])
{
// Storing the graph
for (int i = 0; i < m; ++i) {
int u = edges[i][0],
v = edges[i][1],
c = edges[i][2];
g[u].push_back({ v, c });
}
// Initializing dis array to a
// large value
for (int i = 2; i <= n; ++i) {
dist[i] = INF;
}
// Initialize a priority queue
priority_queue<pair<int, int>,
vector<pair<int, int> >,
greater<pair<int, int> > >
pq;
pq.push({ 0, 1 });
// Base Cases
dist[1] = 0;
route[1] = 1;
// Loop while priority queue is
// not empty
while (!pq.empty()) {
int d = pq.top().first;
int u = pq.top().second;
pq.pop();
// if d is greater than distance
// of the node
if (d > dist[u])
continue;
// Traversing all its neighbours
for (auto e : g[u]) {
int v = e.first;
int c = e.second;
if (c + d > dist[v])
continue;
// Path found of same distance
if (c + d == dist[v]) {
route[v] += route[u];
}
// New path found for lesser
// distance
if (c + d < dist[v]) {
dist[v] = c + d;
route[v] = route[u];
// Pushing in priority
// queue
pq.push({ dist[v], v });
}
}
}
}
// Driver Code
int main()
{
// Given Input
int n = 4;
int m = 5;
int edges[m][3] = { { 1, 4, 5 },
{ 1, 2, 4 },
{ 2, 4, 5 },
{ 1, 3, 2 },
{ 3, 4, 3 } };
// Function Call
countDistinctShortestPaths(n, m, edges);
cout << route[n] << endl;
return 0;
}
2
Complejidad temporal: O(MLogN)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por anuragiiit y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA