我有一个赋值，要求我计算给定一个完整无向图的最短路径。给出了一个完全无向图，基本算法(BFS和DFS(可以提供最短路径。考虑到它是一个完全无向图，我想知道使用BFS或DFS是否会产生相同的输出。
我假设图形使用非负权重进行加权
- 最短路径在未加权完全图中是平凡的
- 在无向图中，负权重边将创建一个负权重循环。在这样的图中没有最短路径，因为你总是可以通过添加负循环来改进它
我还假设您正在寻找两个给定顶点之间的最短路径，因为这是DFS和BFS真正适用的唯一最短路径任务。
- 要找到所有单个源的最短路径，您可以使用Dijkstra
- 要找到所有对的最短路径，你可以使用Floyd Warshall
如果图是有限的，DFS和BFS都会给你最短的路径。如果有多个最短路径，则可以同时执行DFS和BFS，以便它们返回所有路径。否则，它们不能保证给你相同的最短路径——这甚至不能保证相同算法的不同实现，它可能会根据边的顺序而不同。
DFS和BFS都将具有可怕的时间复杂性O(n！(，因为它们将遍历整个问题空间，找到从源到目标的所有可能路径。此外，BFS将具有更大的空间复杂性(再次为O(n！((。
对于DFS和BFS，这种复杂性在平均情况下可以通过保持"；当前最佳"；修剪那些无法战胜它的树枝(因为它们的长度已经更差了(。但你仍然远远没有达到更合适的算法的速度，比如Dijkstra或A*