---

Recursive Exploration Depth First Breadth First Dijkstra A Star

Unweighted Graph Weighted Graph

Why you not have canvas?

Path hops:

Path cost:

---

Think about the todo-list collection

A common pattern amongst the search algorithms (with the semi-exception of recursive exploration) is that they all build a collection which stores paths (or in some implementations nodes) that should be explored. I call this the search "todo" list.

Here is an example. Dijkstra uses a PriorityQueue to store the todo list. Change the collection type to switch between Breadth First Search and A Star.

function dijkstras(startNode, goal) {
    pQueue = PriorityQueue()
    pQueue.enqueue(newPath(startNode), 0)
    seen = Set();
    while !pQueue.isEmpty(): 
        currPath = pQueue.dequeue()
        currState = last(currPath);
        if(currState is goal) return currPath;
        if(seen contains currState) continue;
        seen.add(currState);
        for nextState in getNextStates(currState)
            path = newPath(currPath, nextState);
            pQueue.enqueue(path, getCost(path));
        }
    }
    // failed to find a path
}

The fundamental difference between Depth First Search, Breadth First Search, Dijkstra and A Star is the collection used to represent the "todo" list of paths to process.

Algorithm	Todo Collection	Benefit
Depth First Search	Stack	Uses little memory
Breadth First Search	Queue	Finds shortest hops
Dijkstra's Algorithm	Priority Queue	Finds shortest path
A Star	Priority Queue	Finds shortest path fast

---

Worth Thinking About

In all cases Recursive Exploration is the same of Depth First Search.

Breadth first search always finds the shortest path for unweighted graphs, but not for weighted graphs.

For graphs with unweighted edges, Breadth First Search is the same as Dijkstra's.