贝尔曼-福特算法(Bellman–Ford algorithm )油管最好...

The principle of Relaxation.

- v vertices → (v-1) iterations

! that's the key point of Bellman-Ford

- the order of the vertices that you picked doesn't matter.... Well because of the (v-1) iterations.

- Question about negative weight: Note: regard negative path weight as cost! Not value. If there are negative cycles, the search for a shortest path will go on forever.

If there exists a negative cycle in the graph, then no shortest path.

- the result is the shortest path from src to all vertices.(just like dijk... But dijk doesn't allow negative edge weight.

SUM: dij--vertices. Bellman-Ford--edges. (Slower but versatile