Shorted Path - Directed Weighted Graph

Dijkstra Algorithm

Key Idea

1. Greedy. Utilize Priority Queue, to find the NEAREST node SO FAR. And calculate distance (from start) to the neighbors of it. If there is SMALLER distance, update, and push that neighbor into the Priority Queue
2. With BFS style

Time Complexity

O(ElogV)

* Each `V` should enter the PQ at least ONCE.
* For each `V`, need to calculate NEW distance (to the `start`)
* Finally, around O(ElogV)

Pre-Condition to Utilize Dijkstra

1. Directed Weighted graph

2. No negative weight. But why?

   标准Dijkstra算法是计算最短路径的，但是为什么Dijkstra算法不允许存在负权重边么？

   因为Dijkstra计算最短路径的正确性依赖一个前提：路径中每增加一条边，路径的总权重就会增加。

   其实把这个结论反过来也是OK的：

   如果想计算最长路径，路径中每增加一条边，路径的总权重就会减少。要是能够满足这个条件，也可以用Dijkstra算法。

   比如LC1514

Key Points

• About the code template Why do we need this code piece?

    if distToCurrentNode > distToNode[currentNode] {
        continue
    }
  

  This can improve the performance if a node with a larger distance get into the priority queue before the smallest distance

Problems