Dado un gráfico no dirigido ponderado G y un entero S , la tarea es imprimir las distancias de los caminos más cortos y el número de caminos más cortos para cada Node desde un vértice dado, S.
Ejemplos:
Entrada: S = 1, G =
Salida: Las distancias de las rutas más cortas son: 0 1 2 4 5 3 2 1 3
Los números de las rutas más cortas son: 1 1 1 2 3 1 1 1 2
Explicación:
- La distancia de los caminos más cortos al vértice 1 es 0 y solo hay 1 de esos caminos, que es {1}.
- La distancia de los caminos más cortos al vértice 2 es 1 y solo hay 1 de esos caminos, que es {1→2}.
- La distancia de los caminos más cortos al vértice 3 es 2 y solo hay 1 de esos caminos, que es {1→2→3}.
- La distancia de los caminos más cortos al vértice 4 es 4 y existen 2 de esos caminos, que son {{1→2→3→4}, {1→2→3→6→4}}.
- La distancia de los caminos más cortos al vértice 5 es 5 y existen 3 de esos caminos, que son {{1→2→3→4→5}, {1→2→3→6→4→5}, {1→ 2→3→6→5}}.
- La distancia de los caminos más cortos al vértice 6 es 3 y solo hay 1 de esos caminos, que es {1→2→3→6}.
- La distancia de los caminos más cortos al vértice 7 es 2 y solo hay 1 de esos caminos, que es {1→8→7}.
- La distancia de los caminos más cortos al vértice 8 es 1 y solo hay 1 de esos caminos, que es {1→8}.
- La distancia de los caminos más cortos al vértice 9 es 3 y existen 2 de esos caminos, que son {{1→8→9}, {1→2→3→9}}.
Enfoque: El problema dado se puede resolver utilizando el Algoritmo de Dijkstra . Siga los pasos a continuación para resolver el problema:
- Forme la Lista de adyacencia del gráfico dado usando ArrayList<ArrayList<>> y guárdela en una variable, digamos adj.
- Inicialice dos enteros, Arrays dice Dist[] y Paths[] todos los elementos como 0 para almacenar las distancias más cortas de cada Node y contar las rutas con la distancia más corta desde el Node de origen, S .
- Defina una función, diga Dijkstra() para encontrar las distancias más cortas de cada Node y cuente las rutas con la distancia más corta:
- Inicialice un PriorityQueue mínimo, por ejemplo, PQ y un HashSet of Strings , por ejemplo, establecido para almacenar si se visita el borde o no.
- Asigne 0 a Dist[S] y 1 a Paths[S].
- Ahora itere hasta que PQ no esté vacío() y realice las siguientes operaciones:
- Encuentre el Node superior del PQ y almacene el valor del Node en una variable u .
- Pop el elemento superior de PQ.
- Iterar sobre ArrayList adj[u] y realizar las siguientes operaciones
- Almacene el Node adyacente en un valor variable y el costo del borde en un costo variable :
- Si se visita el borde {u, to} , continúe.
- Si dist[to] es mayor que dist[u]+cost, entonces asigne dist[u]+cost a dist[to] y luego asigne Paths[u] a Paths[to].
- De lo contrario, si Paths[to] es igual a dist[u]+cost, entonces incremente Paths[to] en 1.
- Ahora, Mark, el borde actual {u, to} visitado en liquidado .
- Llame a la función Dijkstra() .
- Finalmente, imprima Arrays dist[] y Paths[] .
A continuación se muestra la implementación del enfoque anterior:
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG {
// Node class
static class Node implements Comparator<Node> {
// Stores the node
public int node;
// Stores the weight
// of the edge
public int cost;
public Node() {}
// Constructor
public Node(int node, int cost)
{
this.node = node;
this.cost = cost;
}
// Costume comparator
@Override
public int compare(Node node1, Node node2)
{
if (node1.cost < node2.cost)
return -1;
if (node1.cost > node2.cost)
return 1;
return 0;
}
}
// Function to insert a node
// in adjacency list
static void addEdge(ArrayList<ArrayList<Node> > adj,
int x, int y, int w)
{
adj.get(x).add(new Node(y, w));
adj.get(y).add(new Node(x, w));
}
// Auxiliary function to find shortest paths using
// Dijekstra
static void dijkstra(ArrayList<ArrayList<Node> > adj,
int src, int n, int dist[],
int paths[])
{
// Stores the distances of every node in shortest
// order
PriorityQueue<Node> pq
= new PriorityQueue<Node>(n + 1, new Node());
// Stores if a vertex has been visited or not
Set<String> settled = new HashSet<String>();
// Adds the source node with 0 distance to pq
pq.add(new Node(src, 0));
dist[src] = 0;
paths[src] = 1;
// While pq is not empty()
while (!pq.isEmpty()) {
// Stores the top node of pq
int u = pq.peek().node;
// Stores the distance
// of node u from s
int d = pq.peek().cost;
// Pop the top element
pq.poll();
for (int i = 0; i < adj.get(u).size(); i++) {
int to = adj.get(u).get(i).node;
int cost = adj.get(u).get(i).cost;
// If edge is marked
if (settled.contains(to + " " + u))
continue;
// If dist[to] is greater
// than dist[u] + cost
if (dist[to] > dist[u] + cost) {
// Add the node to to the pq
pq.add(new Node(to, d + cost));
// Update dist[to]
dist[to] = dist[u] + cost;
// Update paths[to]
paths[to] = paths[u];
}
// Otherwise
else if (dist[to] == dist[u] + cost) {
paths[to] = (paths[to] + paths[u]);
}
// Mark the edge visited
settled.add(to + " " + u);
}
}
}
// Function to find the count of shortest path and
// distances from source node to every other node
static void
findShortestPaths(ArrayList<ArrayList<Node> > adj,
int s, int n)
{
// Stores the distances of a
// node from source node
int[] dist = new int[n + 5];
// Stores the count of shortest
// paths of a node from
// source node
int[] paths = new int[n + 5];
for (int i = 0; i <= n; i++)
dist[i] = Integer.MAX_VALUE;
for (int i = 0; i <= n; i++)
paths[i] = 0;
// Function call to find
// the shortest paths
dijkstra(adj, s, n, dist, paths);
System.out.print("Shortest Paths distances are : ");
for (int i = 1; i <= n; i++) {
System.out.print(dist[i] + " ");
}
System.out.println();
System.out.print(
"Numbers of the shortest Paths are: ");
for (int i = 1; i <= n; i++)
System.out.print(paths[i] + " ");
}
// Driver Code
public static void main(String[] args)
{
// Input
int N = 9;
int M = 14;
ArrayList<ArrayList<Node> > adj = new ArrayList<>();
for (int i = 0; i <= N; i++) {
adj.add(new ArrayList<Node>());
}
addEdge(adj, 1, 2, 1);
addEdge(adj, 2, 3, 1);
addEdge(adj, 3, 4, 2);
addEdge(adj, 4, 5, 1);
addEdge(adj, 5, 6, 2);
addEdge(adj, 6, 7, 2);
addEdge(adj, 7, 8, 1);
addEdge(adj, 8, 1, 1);
addEdge(adj, 2, 8, 2);
addEdge(adj, 3, 9, 1);
addEdge(adj, 8, 9, 2);
addEdge(adj, 7, 9, 2);
addEdge(adj, 3, 6, 1);
addEdge(adj, 4, 6, 1);
// Function call
findShortestPaths(adj, 1, N);
}
}
Producción:
Shortest Paths distances are : 0 1 2 4 5 3 2 1 3 Numbers of the shortest Paths are: 1 1 1 2 3 1 1 1 2
Complejidad de tiempo: O(M + N * log(N))
Espacio auxiliar: O(M)
Publicación traducida automáticamente
Artículo escrito por jigarnainuji2001 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA