Skip to content

Commit a755ffd

Browse files
gazeldxgazeldx
committed
743-network-delay-time.md Added a Common graph theory algorithm comparison table.
1 parent 7753159 commit a755ffd

4 files changed

Lines changed: 37 additions & 4 deletions

File tree

‎en/1-1000/743-network-delay-time.md‎

Lines changed: 15 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -41,13 +41,26 @@ We will send a signal from a given node `k`. Return _the **minimum** time it tak
4141
## Intuition
4242
We can solve it via both **Bellman-Ford algorithm** and **Dijkstra's algorithm**.
4343

44-
`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.
44+
### Bellman-Ford Algorithm
45+
Here is an animation about _Bellman-Ford algorithm_:
46+
47+
![](../../images/graph_Bellman-Ford_algorithm_animation.gif)
48+
49+
* `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.
4550
The following code will introduce how to optimize.
4651

47-
`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.
52+
* `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.
4853

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

56+
### Common graph theory algorithm comparison table
57+
|Algorithm name|Main application scenarios|Optimization methods|Importance|Difficulty|min_distances|Additional application scenarios|
58+
|--------------|--------------------------|--------------------|----------|----------|-------------|--------------------------------|
59+
|[Prim's algorithm](../1001-2000/1584-min-cost-to-connect-all-points.md) |Minimum Spanning Tree |Heap Sort |Important |Medium |Used||
60+
|[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)|
61+
|[Dijkstra's algorithm](../1001-2000/1514-path-with-maximum-probability.md) |Single-Source Shortest Path |Heap Sort |Very important|Medium |Used||
62+
|[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)|
63+
5164
## Complexity
5265
**V**: vertex count, **E**: Edge count.
5366

‎en/3001-4000/unorganized.md‎

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -59,6 +59,12 @@ The improved way with a queue is commonly more efficient. Relaxing **All Edges**
5959
* The time complexity of `Floyd–Warshall algorithm` is `V * V * V`. For a dense graph, `Floyd–Warshall algorithm` is still faster.
6060
* `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.
6161

62+
|Algorithm name|Key implementation methods|
63+
|Prim's algorithm||
64+
|Kruskal's algorithm|Union-Find|
65+
|Dijkstra's algorithm||
66+
|Bellman-Ford algorithm||
67+
6268
## Others
6369
* Find all the prime numbers within 1000000.
6470

‎images/graph_Bellman-Ford_algorithm_animation.gif‎

22.9 KB
Loading

‎zh/1-1000/743-network-delay-time.md‎

Lines changed: 16 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -43,12 +43,26 @@
4343
## 思路
4444
本题可用 **Bellman-Ford算法** 或 **Dijkstra算法** 解决。
4545

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

48-
`Dijkstra算法`因为始终走最短路径，所以执行**效率高**！但代码量大，无法处理`边`权值为**负数**的情况。
49+
![](../../images/graph_Bellman-Ford_algorithm_animation.gif)
50+
51+
* `Bellman-Ford`算法代码量少，还能处理`边`权值为**负数**的情况，但如果没有被优化过，运行得比较慢。下文代码会介绍如何优化。
52+
53+
* `Dijkstra算法`因为始终走最短路径，所以执行**效率高**！但代码量大，无法处理`边`权值为**负数**的情况。
4954

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

57+
* 常见图论算法对比表：
58+
59+
|算法名称|主要的适用场景|优化方式|重要程度|难度|min_distances|额外的适用场景|
60+
|-------|-----------|-------|-------|---|-------------|------------|
61+
|[Prim算法](../1001-2000/1584-min-cost-to-connect-all-points.md) |最小生成树 |堆排序 |重要 |中等|用到||
62+
|[Kruskal算法](../1001-2000/1584-min-cost-to-connect-all-points-2.md)|最小生成树 |堆排序 |重要 |较难|不用|相关场景：[无向图环检测](./684-redundant-connection.md),<br>[有向图环检测](./685-redundant-connection-ii.md)|
63+
|[Dijkstra算法](../1001-2000/1514-path-with-maximum-probability.md) |单源最短路径|堆排序 |非常重要|中等|用到||
64+
|[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)|
65+
5266
## 复杂度
5367
**V**: 顶点数量，**E**: 边的数量。
5468

0 commit comments

Comments
 (0)