原文:
给定一个无向未加权的图和两个节点作为源和目的地，任务是打印给定源和目的地之间最短长度的所有路径。 例:
输入:源= 0，目的地= 5
输出:t2【0->1->3->5 0->2->3->5 0->1->4->5 t6】说明: 以上路径长度均为 3，为 0 到 5 之间最短距离。 输入:来源= 0，目的地= 4
输出:t2 0->1->4
方法:是对一个图进行 。以下是步骤:
- 从源顶点开始 bfs 遍历。
- 进行 bfs 时，存储到每个其他节点的最短距离，并为每个节点维护一个父向量。
- 将源节点的父节点设为-【1】。对于每个节点，它将存储它与源节点距离最短的所有父节点。
- 使用父阵列恢复所有路径。在任何时刻，我们都会在路径数组中推一个顶点，然后调用它的所有父节点。
- 如果我们在上面的步骤中遇到“-1”，那么这意味着已经找到了一个路径，并且可以存储在 path 数组中。
以下是上述方法的实现:
cpp14
// cpp program for the above approach
#include
using namespace std;
// function to form edge between
// two vertices src and dest
void add_edge(vector 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 >& paths,
vector& path,
vector 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 source vertex
void bfs(vector adj[],
vector parent[],
int n, int start)
{
// dist will contain shortest distance
// from start to every other vertex
vector dist(n, int_max);
queue q;
// insert source vertex in queue and make
// its parent -1 and distance 0
q.push(start);
parent[start] = { -1 };
dist[start] = 0;
// until 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 adj[],
int n, int start, int end)
{
vector > paths;
vector path;
vector 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 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;
}
java 语言(一种计算机语言，尤用于创建网站)
/*package whatever //do not write package name here */
import java.io.*;
import java.util.*;
class gfg {
// function to form edge between
// two vertices src and dest
static void add_edge(arraylist> adj, int src, int dest){
adj.get(src).add(dest);
adj.get(dest).add(src);
}
// function which finds all the paths
// and stores it in paths array
static void find_paths(arraylist> paths, arraylist path,
arraylist> parent, int n, int u) {
// base case
if (u == -1) {
paths.add(new arraylist<>(path));
return;
}
// loop for all the parents
// of the given vertex
for (int par : parent.get(u)) {
// insert the current
// vertex in path
path.add(u);
// recursive call for its parent
find_paths(paths, path, parent, n, par);
// remove the current vertex
path.remove(path.size()-1);
}
}
// function which performs bfs
// from the given source vertex
static void bfs(arraylist> adj, arraylist> parent,
int n, int start) {
// dist will contain shortest distance
// from start to every other vertex
int[] dist = new int[n];
arrays.fill(dist, integer.max_value);
queue q = new linkedlist<>();
// insert source vertex in queue and make
// its parent -1 and distance 0
q.offer(start);
parent.get(start).clear();
parent.get(start).add(-1);
dist[start] = 0;
// until queue is empty
while (!q.isempty()) {
int u = q.poll();
for (int v : adj.get(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.offer(v);
parent.get(v).clear();
parent.get(v).add(u);
}
else if (dist[v] == dist[u] 1) {
// another candidate parent for
// shortes path found
parent.get(v).add(u);
}
}
}
}
// function which prints all the paths
// from start to end
static void print_paths(arraylist> adj, int n, int start, int end){
arraylist> paths = new arraylist<>();
arraylist path = new arraylist<>();
arraylist> parent = new arraylist<>();
for(int i = 0; i < n; i ){
parent.add(new arraylist<>());
}
// function call to bfs
bfs(adj, parent, n, start);
// function call to find_paths
find_paths(paths, path, parent, n, end);
for (arraylist v : paths) {
// since paths contain each
// path in reverse order,
// so reverse it
collections.reverse(v);
// print node for the current path
for (int u : v)
system.out.print(u " ");
system.out.println();
}
}
public static void main (string[] args)
{
// number of vertices
int n = 6;
// array of vectors is used
// to store the graph
// in the form of an adjacency list
arraylist> adj = new arraylist<>();
for(int i = 0; i < n; i ){
adj.add(new arraylist<>());
}
// 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);
}
}
// this code is contributed by ayush123ngp.
python 3
# python program for the above approach
# function to form edge between
# two vertices src and dest
from typing import list
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 source 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
# until 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
output:
0 1 3 5
0 2 3 5
0 1 4 5
时间复杂度: o(v e) 其中 v 为顶点数，e 为边数。 辅助空间: o(v) 其中 v 为顶点数。
麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处
