We can solve it via both**Bellman-Ford algorithm** and**Dijkstra's algorithm**.

`Bellman-Ford algorithm` has less code and can handle the situation of**negative** edge weights, but it is slower than`Dijkstra's algorithm` if it is not optimized.

Here is an animation about_Bellman-Ford algorithm_:

*`Bellman-Ford algorithm` has less code and can handle the situation of**negative** edge weights, but it is slower than`Dijkstra's algorithm` if it is not optimized.

The following code will introduce how to optimize.

`Dijkstra's algorithm` always takes the shortest path, so it is more efficient, but it requires writing more code and it cannot handle the situation of**negative** edge weights.

*`Dijkstra's algorithm` always takes the shortest path, so it is more efficient, but it requires writing more code and it cannot handle the situation of**negative** edge weights.

For a detailed description of**Dijkstra's algorithm**, please refer to[1514. Path with Maximum Probability](../1001-2000/1514-path-with-maximum-probability.md).

|Algorithm name|Main application scenarios|Optimization methods|Importance|Difficulty|min_distances|Additional application scenarios|

|--------------|--------------------------|--------------------|----------|----------|-------------|--------------------------------|

|[Prim's algorithm](../1001-2000/1584-min-cost-to-connect-all-points.md)|Minimum Spanning Tree|Heap Sort|Important|Medium|Used||

|[Kruskal's algorithm](../1001-2000/1584-min-cost-to-connect-all-points-2.md)|Minimum Spanning Tree|Heap Sort|important|Relatively hard|Not used|Relative scenarios:[Undirected Graph Cycle Detection](./684-redundant-connection.md),[Directed Graph Cycle Detection](./685-redundant-connection-ii.md)|

|[Dijkstra's algorithm](../1001-2000/1514-path-with-maximum-probability.md)|Single-Source Shortest Path|Heap Sort|Very important|Medium|Used||

|[Bellman-Ford algorithm](./743-network-delay-time.md)|Single-Source Shortest Path|Queue-Improved|Very Important|Easy|Used|Negative Edge Weights,<br>[Detect Negative Cycles](https://www.geeksforgeeks.org/detect-negative-cycle-graph-bellman-ford/),<br>[Shortest Hop-Bounded Paths](./787-cheapest-flights-within-k-stops.md)|

**V**: vertex count,**E**: Edge count.

* The time complexity of`Floyd–Warshall algorithm` is`V * V * V`. For a dense graph,`Floyd–Warshall algorithm` is still faster.

*`A* algorithm` use a`priority queue`,`pop()` to get the vertex closest to the destination vertex. We need to choose**proper math formula** to determine which one is the closest. We to the very near place of destination vertex, we can use some special method to make it can handle the last part.

|Algorithm name|Key implementation methods|

|Prim's algorithm||

|Kruskal's algorithm|Union-Find|

|Dijkstra's algorithm||

|Bellman-Ford algorithm||

* Find all the prime numbers within 1000000.

本题可用**Bellman-Ford算法** 或**Dijkstra算法** 解决。

`Bellman-Ford`算法代码量少，还能处理`边`权值为**负数**的情况，但如果没有被优化过，运行得比较慢。下文代码会介绍如何优化。

*Bellman-Ford算法*的动画演示：

`Dijkstra算法`因为始终走最短路径，所以执行**效率高**！但代码量大，无法处理`边`权值为**负数**的情况。

*`Bellman-Ford`算法代码量少，还能处理`边`权值为**负数**的情况，但如果没有被优化过，运行得比较慢。下文代码会介绍如何优化。

*`Dijkstra算法`因为始终走最短路径，所以执行**效率高**！但代码量大，无法处理`边`权值为**负数**的情况。

**Dijkstra算法**的详细说明，请参考[1514. 概率最大的路径](../1001-2000/1514-path-with-maximum-probability.md)。

* 常见图论算法对比表：

|算法名称|主要的适用场景|优化方式|重要程度|难度|min_distances|额外的适用场景|

|-------|-----------|-------|-------|---|-------------|------------|

|[Prim算法](../1001-2000/1584-min-cost-to-connect-all-points.md)|最小生成树|堆排序|重要|中等|用到||

|[Kruskal算法](../1001-2000/1584-min-cost-to-connect-all-points-2.md)|最小生成树|堆排序|重要|较难|不用|相关场景：[无向图环检测](./684-redundant-connection.md),<br>[有向图环检测](./685-redundant-connection-ii.md)|

|[Dijkstra算法](../1001-2000/1514-path-with-maximum-probability.md)|单源最短路径|堆排序|非常重要|中等|用到||

|[Bellman-Ford算法](./743-network-delay-time.md)|单源最短路径|~~队列~~`集合`优化|非常重要|简单|用到|负边权值，[负环检测](https://www.geeksforgeeks.org/detect-negative-cycle-graph-bellman-ford/),<br>[限定步数最短路径](./787-cheapest-flights-within-k-stops.md)|

**V**: 顶点数量，**E**: 边的数量。