Dijkstra的有Ø运行时间（| E | + | V |登录| V |）和蛮力BFS为O的运行时间（| E | + | V |）
那么，为什么是Dijkstra的更优？它似乎具有更高的运行时间。
编辑：请参阅明显的答案。原来我的运行时间分析在加权图（基本上蛮力）使用BFS最短路径不正确。在加权图使用蛮力BFS为O的上界（V！）。 Dijstra的是更理想的。
我假设你用蛮力意味着路径的所有组合和选择最快的。不过这需要你使用BFS（可能）的次指数数量和在这种情况下，你不能说时间复杂度为O（| V | + | E |）。 O（| V | + | E |）是，如果你使用BFS的恒定时间量。我提到为了说明的，你必须表明，Dijkstra算法比蛮力BFS更快的路径可能性量图表的两个例子，因为后者取决于有多少可能性，你的路径。
具有根部（起点）平衡二叉树，并且每个顶点具有2个孩子除叶子和目标顶点作为叶子之一。如果从根开始，你有2所选择的路径。如果你去他们中的一个，您有进一步的2个选择，并依此类推，直到你在目标顶点。这使得2 * 2 * ... * 2路的可能性，它是乘日志（| V |）-1倍。这是O（n）。这给出了蛮力BFS算法为O（n ^ 2 +纳米）比迪杰斯特拉较慢的运行时间。
全图：假设你开始在V1和目标是VN，你可以在V1开始，为下一个顶点V1的可能性。在第二个顶点你有V-2的可能性，在第三个V-3等，直到你在Vn的。这使得V-1 * V-2 * ... * 3 * 2 * 1 = O（（V-1）！）的可能路径数，这给蛮力BFS算法的指数运行时间。
我们可以看到，后者为上限。下界可以是一个曲线图，其是一个路径，其中两个算法需要O（n）的时间。我们可以得出结论，这可能是在所有的场合，Dijkstra算法或者是快还是一样快，蛮力BFS算法。
Dijkstra的有O(|E| + |V|log|V|)运行时间，但它可以在一个加权图源和目标节点之间的最短路径。 BFS有O(|E| + |V|)的运行时间，但是当你所有的边缘有相同的权重，只找到源和目标节点之间的最短路径。如果你所有的边缘有相同的重量，的确没有必要运行Dijkstra算法。