Best First Search

Usage: Find the shortest path cost from a single node to any other nodes in the graph.

Basic methods:

1. Data structure: Priority Queue(min heap)

2. Initialize: <source node, 0>

3. For each step

Expand: pop the node with the smallest distance from the source. If expanded before, do not generate again

4. Generate: generate all neighbors <nei, dist + weight(parent -> child)>

If dist + weigh >= dist(child), ignore

If <= dist(child), add to pq

5. Termination condition: pq.isEmpty() or the target node is expanded

Properties:

1. One node can only be expanded once and can be generated more than once, cost can be reduced over time.

2. All the costs of the nodes that are expanded are monotonically non-decreasing.

3. TC: for a graph with n nodes and the connectivity of the node is constant. O(nlogn) / O(ElogV)

4. When a node is popped out for expansion, its value is fixed which is equal to the shortest distance from the start node.