> For the complete documentation index, see [llms.txt](https://xiaoyang-liu.gitbook.io/programming-notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://xiaoyang-liu.gitbook.io/programming-notes/computer-science/data-structures/shortest-paths.md).

# Shortest Paths

## BFS v.s. DFS for Path Finding

* BFS returns path with shortest number of edges.
* Time efficiency is similar for both algorithms.
* Space Efficiency is quite different.
* * DFS is worse for spindly graphs. (Call stack gets very deep.)
* * BFS is worse for bushy graphs. (Queue gets very large.)
* Track the `distTo` and `edgeTo` arrays requires `Θ(V)` memory.

## Shortest Path Tree

* For every vertex v (which is not s) in the graph, find the shortest path from s to v.
* Combine all the edges that the algorithm found above.

## Dijkstra's Algorithm

Instead of BFS, an algorithm which takes into account edge distances (edge weights) is created.

* Create a priority queue.
* Add s to the priority queue with priority 0. 
* Add all other vertices to the priority queue with priority infinity.
* While the priority queue is not empty, and relax all of the edges going out from the vertex.

As long as the edges are all non-negative, Dijkstra's is guaranteed to be optimal.

### Relax

* For the popped vertex v, iterate through its edges.
* For the edge (v,w), compare the `currentBestDistToV + weight(v,w)` and `currentBestDistToW`.
* If the former is smaller, set the `currentBestDistToW = currentBestDistToV + weight(v,w)`, and set `edgeTo[w] = v`.
* Never relax edges that point to already visited vertices.

### Code

```
def dijkstras(source):
    PQ.add(source, 0)
    For all other vertices, v, PQ.add(v, infinity)
    while PQ is not empty:
        p = PQ.removeSmallest()
        relax(all edges from p)

def relax(edge p,q):
   if q is visited (or q is not in PQ):
       return

   if distTo[p] + weight(edge) < distTo[q]:
       distTo[q] = distTo[p] + w
       edgeTo[q] = p
       PQ.changePriority(q, distTo[q])
```

### Proof

* At start, `distTo[source] = 0`.
* After relaxing all edges from source, assume v1 is the closet vertex to the source.
* Suppose there's another path `(s,va,vb,...,v1)`, which is shorter than `(s,v1)`.
* Since `(s,va)` is longer than `(s,v1)`, that path doesn't exist.
* Thus, v1 is the closet vertex to the source, and that argument is still valid for all the edges of v1.

### Runtime

Dijkstra's Algorithm is based on the PQ.

Overall runtime: `O(V log(V) + V log(V) + E log(V))`

Connected graph: `O(E log V)` (E > V)

* `add`: V, each costing `O(log V)` time.
* `removeSmallest`: V, each costing `O(log V)` time.
* `changePriority`: E, each costing `O(log V)` time.