假设我有一个工作 dijkstra 的最短路径方法，我如何使用它来确定有向图是否是强连接的？
问问题
400 次
1 回答
2
为什么最短路径算法说所有节点都可以从输入节点到达？
你在说什么最短路径算法？
强连通有向图中是否存在 s 最短路径之类的东西？
只要一个图是连通的，它就包含一条最短路径。不同的算法，如 bfs、dijkstra's、Belman ford 等，都存在于寻找具有独特属性的图中的最短路径
为什么如果你反转图表，所有节点仍然可以访问？
仅当图是强连接时才成立。此外，这只是确定图是否强连接的众多方法之一。另一种方法是从每个节点运行 dfs，只要每次都触摸每个节点，直到最后一个节点，图是强连接的。
这如何证明图是强连接的？
我不知道证据，但存在一个证据，你可以从谷歌找到它。
有什么地方可以找到代码来确定图形是否使用最短路径算法强连接？
要确定一个图是否是强连接的，首先通过该图运行 dfs。如果所有节点都可达，则反转边的方向并再次运行dfs，如果所有节点仍然可达，则图是强连接的
我自己如何使用最短路径算法对此进行编码？
在 Google 上查找 dfs
于 2016-05-20T02:22:05.913 回答