为何要考虑使用Bellman-Ford算法？探讨其实际应用场景

我需要查找两个顶点之间的最短路径，整理了几种场景下的算法选择：

• 场景A：无负权边，邻接表存储

  • 单源最短路径：运行一次Dijkstra算法，时间复杂度O(V^2)
  • 所有顶点间最短路径：对每个顶点运行Dijkstra，时间复杂度O(V^3)（非完全图中这两种方式效率都不高）

• 场景B：无负权边，邻接矩阵存储

  • 单源最短路径：Dijkstra算法，时间复杂度O(V^2)
  • 所有顶点间最短路径：Floyd-Warshall（FW）算法，时间复杂度O(V^3)

• 场景C：存在负权边（任意存储形式）

  • 单源最短路径：Bellman-Ford算法，时间复杂度O(V^3)
  • 所有顶点间最短路径：FW算法，时间复杂度O(V^3)

这里有个疑问：两者运行时间大致相同（邻接表存储时略有差异），那直接用FW算法是不是能以差不多的时间获取更多信息？

另外，我想知道是否存在必须使用Bellman-Ford算法的实际场景？目前能想到的只有图以邻接表形式存储且存在负权边的情况，但不确定这对FW算法有什么影响，也不知道是否需要先把邻接表转成邻接矩阵再用FW。

内容的提问来源于stack exchange，提问作者idkusrname126