Dado un gráfico dirigido no ponderado, puede ser cíclico o acíclico. Imprime el número de caminos más cortos desde un vértice dado a cada uno de los vértices. Por ejemplo, considere el siguiente gráfico. Hay un camino más corto del vértice 0 al vértice 0 (desde cada vértice hay un solo camino más corto hacia sí mismo), un camino más corto entre el vértice 0 y el vértice 2 (0->2), y hay 4 caminos más cortos diferentes desde el vértice 0 al vértice 6:
1. 0->1->3->4->6
2. 0->1->3->5->6
3. 0->2->3->4->6
4 0->2->3->5->6
La idea es utilizar BFS . Usamos dos arreglos llamados dist[] y paths[], dist[] representa las distancias más cortas desde el vértice de origen y paths[] representa el número de diferentes caminos más cortos desde el vértice de origen a cada uno de los vértices. Inicialmente, todos los elementos en dist[] son infinitos excepto el vértice fuente que es igual a 0, ya que la distancia al vértice fuente desde sí mismo es 0, y todos los elementos en paths[] son 0 excepto el vértice fuente que es igual a 1, ya que cada vértice tiene un único camino más corto hacia sí mismo. después de eso, comenzamos a atravesar el gráfico usando la forma BFS.
Luego, para cada vecino Y de cada vértice X haga:
1) si dist[Y] > dist[X]+1 disminuya dist[Y] a dist[X] +1 y asigne el número de caminos del vértice X al número de caminos del vértice Y.
2) de lo contrario, si dist[Y] = dist[X] + 1, sume el número de caminos del vértice X al número de caminos del vértice Y.
Por ejemplo:
Echemos un vistazo al siguiente gráfico. El vértice de origen es 0. Supongamos que recorremos el vértice 2, verificamos todos sus vecinos, que es solo 3. Dado que el vértice 3 ya fue visitado cuando recorrimos el vértice 1, dist[3] = 2 y paths[3] = 1 La segunda condición es verdadera, por lo que significa que se han encontrado caminos más cortos adicionales, por lo que sumamos al número de caminos del vértice 3, el número de caminos del vértice 2.
La condición igual ocurre cuando recorremos el vértice 5:
C++
// CPP program to count number of shortest
// paths from a given source to every other
// vertex using BFS.
#include <bits/stdc++.h>
using namespace std;
// Traverses graph in BFS manner. It fills
// dist[] and paths[]
void BFS(vector<int> adj[], int src, int dist[],
int paths[], int n)
{
bool visited[n];
for (int i = 0; i < n; i++)
visited[i] = false;
dist[src] = 0;
paths[src] = 1;
queue <int> q;
q.push(src);
visited[src] = true;
while (!q.empty())
{
int curr = q.front();
q.pop();
// For all neighbors of current vertex do:
for (auto x : adj[curr])
{
// if the current vertex is not yet
// visited, then push it to the queue.
if (visited[x] == false)
{
q.push(x);
visited[x] = true;
}
// check if there is a better path.
if (dist[x] > dist[curr] + 1)
{
dist[x] = dist[curr] + 1;
paths[x] = paths[curr];
}
// additional shortest paths found
else if (dist[x] == dist[curr] + 1)
paths[x] += paths[curr];
}
}
}
// function to find number of different
// shortest paths form given vertex s.
// n is number of vertices.
void findShortestPaths(vector<int> adj[],
int s, int n)
{
int dist[n], paths[n];
for (int i = 0; i < n; i++)
dist[i] = INT_MAX;
for (int i = 0; i < n; i++)
paths[i] = 0;
BFS(adj, s, dist, paths, n);
cout << "Numbers of shortest Paths are: ";
for (int i = 0; i < n; i++)
cout << paths[i] << " ";
}
// A utility function to add an edge in a
// directed graph.
void addEdge(vector<int> adj[], int u, int v)
{
adj[u].push_back(v);
}
// Driver code
int main()
{
int n = 7; // Number of vertices
vector <int> adj[n];
addEdge(adj, 0, 1);
addEdge(adj, 0, 2);
addEdge(adj, 1, 2);
addEdge(adj, 1, 3);
addEdge(adj, 2, 3);
addEdge(adj, 3, 4);
addEdge(adj, 3, 5);
addEdge(adj, 4, 6);
addEdge(adj, 5, 6);
findShortestPaths(adj, 0, 7);
return 0;
}
Java
// Java program to count number of shortest
// paths from a given source to every other
// vertex using BFS.
import java.io.*;
import java.util.*;
class GFG
{
// Traverses graph in BFS manner.
// It fills dist[] and paths[]
static void BFS(Vector<Integer>[] adj, int src,
int dist[], int paths[], int n)
{
boolean[] visited = new boolean[n];
for (int i = 0; i < n; i++)
visited[i] = false;
dist[src] = 0;
paths[src] = 1;
Queue<Integer> q = new LinkedList<>();
q.add(src);
visited[src] = true;
while (!q.isEmpty())
{
int curr = q.peek();
q.poll();
// For all neighbors of current vertex do:
for (int x : adj[curr])
{
// if the current vertex is not yet
// visited, then push it to the queue.
if (visited[x] == false)
{
q.add(x);
visited[x] = true;
}
// check if there is a better path.
if (dist[x] > dist[curr] + 1)
{
dist[x] = dist[curr] + 1;
paths[x] = paths[curr];
}
// additional shortest paths found
else if (dist[x] == dist[curr] + 1)
paths[x] += paths[curr];
}
}
}
// function to find number of different
// shortest paths form given vertex s.
// n is number of vertices.
static void findShortestPaths(Vector<Integer> adj[],
int s, int n)
{
int[] dist = new int[n], paths = new int[n];
for (int i = 0; i < n; i++)
dist[i] = Integer.MAX_VALUE;
for (int i = 0; i < n; i++)
paths[i] = 0;
BFS(adj, s, dist, paths, n);
System.out.print("Numbers of shortest Paths are: ");
for (int i = 0; i < n; i++)
System.out.print(paths[i] + " ");
}
// A utility function to add an edge in a
// directed graph.
static void addEdge(Vector<Integer> adj[],
int u, int v)
{
adj[u].add(v);
}
// Driver Code
public static void main(String[] args)
{
int n = 7; // Number of vertices
Vector<Integer>[] adj = new Vector[n];
for (int i = 0; i < n; i++)
adj[i] = new Vector<>();
addEdge(adj, 0, 1);
addEdge(adj, 0, 2);
addEdge(adj, 1, 2);
addEdge(adj, 1, 3);
addEdge(adj, 2, 3);
addEdge(adj, 3, 4);
addEdge(adj, 3, 5);
addEdge(adj, 4, 6);
addEdge(adj, 5, 6);
findShortestPaths(adj, 0, 7);
}
}
// This code is contributed by
// sanjeev2552
Python3
# Python3 program to count number of shortest
# paths from a given source to every other
# vertex using BFS.
from collections import deque
from sys import maxsize as INT_MAX
# Traverses graph in BFS manner. It fills
# dist[] and paths[]
def BFS(adj: list, src: int, dist: list, paths: list, n: int):
visited = [False] * n
dist[src] = 0
paths[src] = 1
q = deque()
q.append(src)
visited[src] = True
while q:
curr = q[0]
q.popleft()
# For all neighbors of current vertex do:
for x in adj[curr]:
# if the current vertex is not yet
# visited, then push it to the queue.
if not visited[x]:
q.append(x)
visited[x] = True
# check if there is a better path.
if dist[x] > dist[curr] + 1:
dist[x] = dist[curr] + 1
paths[x] = paths[curr]
# additional shortest paths found
elif dist[x] == dist[curr] + 1:
paths[x] += paths[curr]
# function to find number of different
# shortest paths form given vertex s.
# n is number of vertices.
def findShortestPaths(adj: list, s: int, n: int):
dist = [INT_MAX] * n
paths = [0] * n
BFS(adj, s, dist, paths, n)
print("Numbers of shortest Paths are:", end=" ")
for i in paths:
print(i, end=" ")
# A utility function to add an edge in a
# directed graph.
def addEdge(adj: list, u: int, v: int):
adj[u].append(v)
# Driver Code
if __name__ == "__main__":
n = 7 # Number of vertices
adj = [0] * n
for i in range(n):
adj[i] = []
addEdge(adj, 0, 1)
addEdge(adj, 0, 2)
addEdge(adj, 1, 2)
addEdge(adj, 1, 3)
addEdge(adj, 2, 3)
addEdge(adj, 3, 4)
addEdge(adj, 3, 5)
addEdge(adj, 4, 6)
addEdge(adj, 5, 6)
findShortestPaths(adj, 0, 7)
# This code is contributed by
# sanjeev2552
C#
// C# program to count number of shortest
// paths from a given source to every other
// vertex using BFS.
using System;
using System.Collections.Generic;
class GFG
{
// Traverses graph in BFS manner.
// It fills dist[] and paths[]
static void BFS(List<int>[] adj, int src,
int []dist, int []paths, int n)
{
bool[] visited = new bool[n];
for (int i = 0; i < n; i++)
visited[i] = false;
dist[src] = 0;
paths[src] = 1;
List<int> q = new List<int>();
q.Add(src);
visited[src] = true;
while (q.Count != 0)
{
int curr = q[0];
q.RemoveAt(0);
// For all neighbors of current vertex do:
foreach (int x in adj[curr])
{
// if the current vertex is not yet
// visited, then push it to the queue.
if (visited[x] == false)
{
q.Add(x);
visited[x] = true;
}
// check if there is a better path.
if (dist[x] > dist[curr] + 1)
{
dist[x] = dist[curr] + 1;
paths[x] = paths[curr];
}
// additional shortest paths found
else if (dist[x] == dist[curr] + 1)
paths[x] += paths[curr];
}
}
}
// function to find number of different
// shortest paths form given vertex s.
// n is number of vertices.
static void findShortestPaths(List<int> []adj,
int s, int n)
{
int[] dist = new int[n], paths = new int[n];
for (int i = 0; i < n; i++)
dist[i] = int.MaxValue;
for (int i = 0; i < n; i++)
paths[i] = 0;
BFS(adj, s, dist, paths, n);
Console.Write("Numbers of shortest Paths are: ");
for (int i = 0; i < n; i++)
Console.Write(paths[i] + " ");
}
// A utility function to add an edge in a
// directed graph.
static void addEdge(List<int> []adj,
int u, int v)
{
adj[u].Add(v);
}
// Driver Code
public static void Main(String[] args)
{
int n = 7; // Number of vertices
List<int>[] adj = new List<int>[n];
for (int i = 0; i < n; i++)
adj[i] = new List<int>();
addEdge(adj, 0, 1);
addEdge(adj, 0, 2);
addEdge(adj, 1, 2);
addEdge(adj, 1, 3);
addEdge(adj, 2, 3);
addEdge(adj, 3, 4);
addEdge(adj, 3, 5);
addEdge(adj, 4, 6);
addEdge(adj, 5, 6);
findShortestPaths(adj, 0, 7);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program to count number of shortest
// paths from a given source to every other
// vertex using BFS.
// Traverses graph in BFS manner.
// It fills dist[] and paths[]
function BFS(adj,src,dist,paths,n)
{
let visited = new Array(n);
for (let i = 0; i < n; i++)
visited[i] = false;
dist[src] = 0;
paths[src] = 1;
let q = [];
q.push(src);
visited[src] = true;
while (q.length!=0)
{
let curr = q[0];
q.shift();
// For all neighbors of current vertex do:
for (let x of adj[curr].values())
{
// if the current vertex is not yet
// visited, then push it to the queue.
if (visited[x] == false)
{
q.push(x);
visited[x] = true;
}
// check if there is a better path.
if (dist[x] > dist[curr] + 1)
{
dist[x] = dist[curr] + 1;
paths[x] = paths[curr];
}
// additional shortest paths found
else if (dist[x] == dist[curr] + 1)
paths[x] += paths[curr];
}
}
}
// function to find number of different
// shortest paths form given vertex s.
// n is number of vertices.
function findShortestPaths(adj,s,n)
{
let dist = new Array(n), paths = new Array(n);
for (let i = 0; i < n; i++)
dist[i] = Number.MAX_VALUE;
for (let i = 0; i < n; i++)
paths[i] = 0;
BFS(adj, s, dist, paths, n);
document.write("Numbers of shortest Paths are: ");
for (let i = 0; i < n; i++)
document.write(paths[i] + " ");
}
// A utility function to add an edge in a
// directed graph.
function addEdge(adj,u,v)
{
adj[u].push(v);
}
// Driver Code
let n = 7; // Number of vertices
let adj = new Array(n);
for (let i = 0; i < n; i++)
adj[i] = [];
addEdge(adj, 0, 1);
addEdge(adj, 0, 2);
addEdge(adj, 1, 2);
addEdge(adj, 1, 3);
addEdge(adj, 2, 3);
addEdge(adj, 3, 4);
addEdge(adj, 3, 5);
addEdge(adj, 4, 6);
addEdge(adj, 5, 6);
findShortestPaths(adj, 0, 7);
// This code is contributed by rag2127
</script>
Producción:
Numbers of shortest Paths are: 1 1 1 2 2 2 4
Tiempo Complejidad : O(V + E)
Publicación traducida automáticamente
Artículo escrito por Shlomi Elhaiani y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA