-[1584. Min Cost to Connect All Points](en/1001-2000/1584-min-cost-to-connect-all-points.md) was solved in_Python, Java, C++, JavaScript, C#, Go, Ruby_ and 2 ways.

-[207. Course Schedule](en/1-1000/207-course-schedule.md) was solved in_Python, Java, C++, C#_ and 2 ways.

-[1514. Path with Maximum Probability](en/1001-2000/1514-path-with-maximum-probability.md) was solved in_Python_ and 2 ways.

-[752. Open the Lock](en/1-1000/752-open-the-lock.md) was solved in_Python_ and 2 ways.

-[743. Network Delay Time](en/1-1000/743-network-delay-time.md) was solved in_Python_ and 2 ways.

-[787. Cheapest Flights Within K Stops](en/1-1000/787-cheapest-flights-within-k-stops.md) was solved in_Python_.

-[1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance](en/1001-2000/1334-find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance.md) was solved in_Python_.

-[752. Open the Lock](en/1-1000/752-open-the-lock.md) was solved in_Python_ and 2 ways.

-[433. Minimum Genetic Mutation](en/1-1000/433-minimum-genetic-mutation.md) was solved in_Python_ and 2 ways.

|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)|

|[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||

|[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||

|[A* search algorithm](./752-open-the-lock.md)|Single-Source Shortest Path|Built-in Heap Sort|Very important|Medium|Not used|It depends||

|[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.

**Breadth-First Search** treats each vertex equally, which inevitably leads to poor performance.

The`A* (A-star) searchalgorithm` calculates the**distance** between each`vertex` and the`target vertex`, and**prioritizes vertices with closer distances**, which is equivalent to indicating which vertex to process next, so the performance is greatly improved!

The_A* (A-star) searchalgorithm_ calculates the**distance** between each`vertex` and the`target vertex`, and**prioritizes vertices with closer distances**, which is equivalent to indicating which vertex to process next, so the performance is greatly improved!

_A* (A-star) search algorithm_ is similar to_Dijkstra's algorithm_, but the`target vertex` of_A* (A-star) search algorithm_ is clear, while that of_Dijkstra's algorithm_ is not._Dijkstra's algorithm_ calculates the`distance` from the`starting vertex` to the`vertex` it reaches.

|算法名称|主要的适用场景|优化方式|重要度|难度|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)|单源最短路径|堆排序优化|很重要|较难|用到|无能力||

|[A* 算法](./752-open-the-lock.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)|多源最短路径|无需优化|较不重要|较难|用到|能处理||

`A* (A-Star) 算法` 会对每一个`顶点`与`目标顶点`的**距离**进行计算，**距离近的顶点优先处理**，相当于为下一步处理哪个顶点指明了方向，因此性能有很大的提升！

`A* (A-Star) 算法` 和`Dijkstra's 算法` 比较像，但`A* 算法`的`目标顶点`是明确的，但`Dijkstra's 算法`不明确。`Dijkstra's 算法`是走到哪个顶点就计算从`起点`到`那个顶点`的距离。

1. 要用`priority_queue`。

2. 计算距离的`启发式函数`要**精心设计**。设计不好，将导致不易察觉的结果错误!