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|Negative weights|Additional application scenarios|

|Algorithm name|Main application scenarios|Optimization methods|Importance|Difficulty|min_<br>distances|Negative weights|Additional application scenarios|

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

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

|[Kruskal's algorithm](../1001-2000/1584-min-cost-to-connect-all-points-2.md)|Minimum Spanning Tree|No need|important|Relatively hard|Not used|Can handle|Relative:[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|Relatively hard|Used|Cannot handle||

|[Bellman-Ford algorithm](./743-network-delay-time.md)|Single-Source Shortest Path|Queue-Improved|Very Important|Easy|Used|Can handle|[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)|

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

|[Kruskal's algorithm](../1001-2000/1584-min-cost-to-connect-all-points-2.md)|Minimum Spanning Tree|No need|important|Relatively hard|Not used|Can handle|Relative:[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|Relatively hard|Used|Cannot handle||

|[Bellman-Ford algorithm](./743-network-delay-time.md)|Single-Source Shortest Path|Queue-Improved|Very Important|Easy|Used|Can handle|[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)|

|[Floyd–Warshall](../1001-2000/1334-find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance.md)|Multi-Source Shortest Path|No need|Less important|Relatively hard|Used|Can handle||

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

</details>

Just like the`Hints` says, you can use**Floyd-Warshallalgorithm** to compute any-point to any-point shortest distances.

Just like the`Hints` says, you can use**Floyd-WarshallAlgorithm** to compute any-point to any-point shortest distances.

Or you can also do**Dijkstra algorithm** from every node due to the weights are non-negative.

Or you can also do**Dijkstra Algorithm** from every node due to the weights are non-negative.

Or you can also do**Queue-Improved Bellman-Ford Algorithm** from every node.

* Time:`O(N^3)`.

|算法名称|主要的适用场景|优化方式|重要度|难度|min_<br>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),[有向图环检测](./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/),[限定步数最短路径](./787-cheapest-flights-within-k-stops.md)|

|[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),[有向图环检测](./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/),[限定步数最短路径](./787-cheapest-flights-within-k-stops.md)|

|[Floyd–Warshall](../1001-2000/1334-find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance.md)|多源最短路径|无需优化|较不重要|较难|用到|能处理||

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

或者，你可以多次调用**Dijkstra 算法**，每次调用时用不同的城市做为`起始城市`。

或者，你可以多次调用**集合优化的 Bellman-Ford 算法**，每次调用时用不同的城市做为`起始城市`。

* Time:`O(N^3)`.

* Space:`O(N^2)`.