查找具有多维前驱数组的图中两个节点之间的所有最短路径

问题描述 投票:1回答:1

所以我一直在试图寻找方法来找到未加权图中两个特定节点之间的所有最短路径,并且我已经编写了代码,直到我建立了一个“前趋”数组来跟踪我的节点已经习惯了到达给定节点。这个数组是一个多维数组,所以例如,如果从A到D的最短路径可以来自A> B> D OR A> C> D,那么前一个数组将如下所示(其中第一行是索引,并且然后下面的行是一个多维数组):

A    | B    | C    | D    | 
---------------------------
     | A    | A    | B    |
---------------------------
     |      |      | C    |

但现在我迷失了如何找到这个前任阵列中的每个排列,以获得可能的最短路径的每种可能组合然后打印出来,例如我想要打印出来:

All shortest paths:
A > B > D
A > C > D

我听说有人说你可以通过递归来做到这一点吗?但我很失落。 (另请注意,我并不太担心时间复杂度)。谢谢你的任何指导!

algorithm graph graph-algorithm breadth-first-search graph-traversal
1个回答
0
投票

我听说有人说你可以通过递归来做到这一点吗?

我不确定他们在说这个时会想到什么,但是我给你一个简单的方法来解决这个问题,它也会在很好的时间内解决这个问题。使用BFS解决这种情况。 IMO,这是你最好的选择。

解:

Example graph:
(A,B,C,D,E)
A->B, A->C, B->D, B->E, C->E, D->E

Source: A, Destination: E
Paths: (marked with # are solution paths)
# A->B->E
# A->C->E
  A->B->D->E
  1. 从源节点开始。保持队列,每个元素有3个信息点: 节点 水平 路径(到现在为止)
  2. 在图表上做一个BFS。在每个级别,检查是否到达目的地。继续这个直到完成。
  3. 当您在某个级别到达目的地时,请不要像通常情况那样停在那里。您需要完全完成此级别,并在完成此级别后停止。
  4. 打印目的地的所有路径,这将是您的答案。

在我们的例子上工作:

  • 队列的每个元素表示为3值元组(节点,级别,路径)

初始队列:(A,0,null)

Level         Queue
 0            (A,0,null)
 1            (B,1,A)
 1            (C,1,A)
 2            (D,2,AB)
 2            (E,2,AB)      #       --> found destination, so, complete L2 fully
 2            (E,2,AC)      #
 3...stop

打印路径:上面的ABE和ACE。

© www.soinside.com 2019 - 2024. All rights reserved.