Вывести все кратчайшие пути между заданным источником и местом назначения в неориентированном графе

Опубликовано: 1 Января, 2022

Учитывая неориентированный и невзвешенный граф и два узла в качестве источника и назначения , задача состоит в том, чтобы напечатать все пути наименьшей длины между заданным источником и местом назначения.
Примеры:

Input: source = 0, destination = 5 
 

Output: 
0 -> 1 -> 3 -> 5
0 -> 2 -> 3 -> 5
0 -> 1 -> 4 -> 5 
Explanation: 
All the above paths are of length 3, which is the shortest distance between 0 and 5.
Input: source = 0, destination = 4 
 

Output: 
0 -> 1 -> 4 
 

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Подход: необходимо выполнить обход в ширину (BFS) для графа. Ниже приведены шаги:

  1. Начать обход BFS с исходной вершины.
  2. При выполнении BFS сохраняйте кратчайшее расстояние до каждого из других узлов, а также поддерживайте родительский вектор для каждого из узлов.
  3. Сделайте родителем исходного узла значение «-1» . Для каждого узла он будет хранить всех родителей, для которых он имеет кратчайшее расстояние от исходного узла.
  4. Восстановить все пути, используя родительский массив. В любой момент мы протолкнем одну вершину в массив путей, а затем вызовем всех ее родителей.
  5. Если мы встречаем «-1» на вышеупомянутых шагах, это означает, что путь был найден и может быть сохранен в массиве путей.

Ниже представлена реализация описанного выше подхода:

cpp14

// Cpp program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to form edge between
// two vertices src and dest
void add_edge(vector< int > adj[],
int src, int dest)
{
adj[src].push_back(dest);
adj[dest].push_back(src);
}
// Function which finds all the paths
// and stores it in paths array
void find_paths(vector<vector< int > >& paths,
vector< int >& path,
vector< int > parent[],
int n, int u)
{
// Base Case
if (u == -1) {
paths.push_back(path);
return ;
}
// Loop for all the parents
// of the given vertex
for ( int par : parent[u]) {
// Insert the current
// vertex in path
path.push_back(u);
// Recursive call for its parent
find_paths(paths, path, parent,
n, par);
// Remove the current vertex
path.pop_back();
}
}
// Function which performs bfs
// from the given souce vertex
void bfs(vector< int > adj[],
vector< int > parent[],
int n, int start)
{
// dist will contain shortest distance
// from start to every other vertex
vector< int > dist(n, INT_MAX);
queue< int > q;
// Insert source vertex in queue and make
// its parent -1 and distance 0
q.push(start);
parent[start] = { -1 };
dist[start] = 0;
// Untill Queue is empty
while (!q.empty()) {
int u = q.front();
q.pop();
for ( int v : adj[u]) {
if (dist[v] > dist[u] + 1) {
// A shorter distance is found
// So erase all the previous parents
// and insert new parent u in parent[v]
dist[v] = dist[u] + 1;
q.push(v);
parent[v].clear();
parent[v].push_back(u);
}
else if (dist[v] == dist[u] + 1) {
// Another candidate parent for
// shortes path found
parent[v].push_back(u);
}
}
}
}
// Function which prints all the paths
// from start to end
void print_paths(vector< int > adj[],
int n, int start, end) int
{
vector<vector< int > > paths;
vector< int > path;
vector< int > parent[n];
// Function call to bfs
bfs(adj, parent, n, start);
// Function call to find_paths
find_paths(paths, path, parent, n, end);
for ( auto v : paths) {
// Since paths contain each
// path in reverse order,
// so reverse it
reverse(v.begin(), v.end());
// Print node for the current path
for ( int u : v)
cout << u << " " ;
cout << endl;
}
}
// Driver Code
int main()
{
// Number of vertices
int n = 6;
// array of vectors is used
// to store the graph
// in the form of an adjacency list
vector< int > adj[n];
// Given Graph
add_edge(adj, 0, 1);
add_edge(adj, 0, 2);
add_edge(adj, 1, 3);
add_edge(adj, 1, 4);
add_edge(adj, 2, 3);
add_edge(adj, 3, 5);
add_edge(adj, 4, 5);
// Given source and destination
int src = 0;
int dest = n - 1;
// Function Call
print_paths(adj, n, src, dest);
return 0;
}

Python3

# Python program for the above approach
# Function to form edge between
# two vertices src and dest
from typing List import
from sys import maxsize
from collections import deque
def add_edge(adj: List [ List [ int ]],
src: int , dest: int ) - > None :
adj[src].append(dest)
adj[dest].append(src)
# Function which finds all the paths
# and stores it in paths array
def find_paths(paths: List [ List [ int ]], path: List [ int ],
parent: List [ List [ int ]], n: int , u: int ) - > None :
# Base Case
if (u = = - 1 ):
paths.append(path.copy())
return
# Loop for all the parents
# of the given vertex
for par in parent[u]:
# Insert the current
# vertex in path
path.append(u)
# Recursive call for its parent
find_paths(paths, path, parent, n, par)
# Remove the current vertex
path.pop()
# Function which performs bfs
# from the given souce vertex
def bfs(adj: List [ List [ int ]],
parent: List [ List [ int ]], n: int ,
start: int ) - > None :
# dist will contain shortest distance
# from start to every other vertex
dist = [maxsize for _ in range (n)]
q = deque()
# Insert source vertex in queue and make
# its parent -1 and distance 0
q.append(start)
parent[start] = [ - 1 ]
dist[start] = 0
# Untill Queue is empty
while q:
u = q[ 0 ]
q.popleft()
for v in adj[u]:
if (dist[v] > dist[u] + 1 ):
# A shorter distance is found
# So erase all the previous parents
# and insert new parent u in parent[v]
dist[v] = dist[u] + 1
q.append(v)
parent[v].clear()
parent[v].append(u)
elif (dist[v] = = dist[u] + 1 ):
# Another candidate parent for
# shortes path found
parent[v].append(u)
# Function which prints all the paths
# from start to end
def print_paths(adj: List [ List [ int ]], n: int ,
start: int , end: int ) - > None :
paths = []
path = []
parent = [[] for _ in range (n)]
# Function call to bfs
bfs(adj, parent, n, start)
# Function call to find_paths
find_paths(paths, path, parent, n, end)
for v in paths:
# Since paths contain each
# path in reverse order,
# so reverse it
v = reversed (v)
# Print node for the current path
for u in v:
print (u, end = " " )
print ()
# Driver Code
if __name__ = = "__main__" :
# Number of vertices
n = 6
# array of vectors is used
# to store the graph
# in the form of an adjacency list
adj = [[] for _ in range (n)]
# Given Graph
add_edge(adj, 0 , 1 )
add_edge(adj, 0 , 2 )
add_edge(adj, 1 , 3 )
add_edge(adj, 1 , 4 )
add_edge(adj, 2 , 3 )
add_edge(adj, 3 , 5 )
add_edge(adj, 4 , 5 )
# Given source and destination
src = 0
dest = n - 1
# Function Call
print_paths(adj, n, src, dest)
# This code is contributed by sanjeev2552
Выход:
 0 1 3 5 
0 2 3 5 
0 1 4 5

Сложность по времени: O (V + E), где V - количество вершин, а E - количество ребер.
Вспомогательное пространство: O (V), где V - количество вершин.

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по доступной для студентов цене и будьте готовы к работе в отрасли. Получите все важные математические концепции для соревновательного программирования с курсом Essential Maths for CP по доступной для студентов цене.

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.