Graph search: BFS, DFS and Dijkstra

Type one edge per line: A-B joins A and B, A-B 4 gives the edge a weight of 4, and A>B makes it one-way. Pick an algorithm, and optionally a start and a goal; without a start, the search begins at the first node alphabetically. The output is the order the nodes are visited, the steps show the queue, stack or distances as they change, and the graph is drawn with each node numbered in visit order and the path to the goal marked in red.

Where a node has several neighbours, they are taken in alphabetical order, the usual rule in class, so your answer matches a worked solution that follows it.

BFS visits the start, then all its neighbours, then all of theirs, spreading out in rings. It keeps a queue: first in, first out. Because it reaches every node at distance 1 before any at distance 2, the first path it finds to a goal has the fewest edges possible, which makes it the right choice for shortest paths when every edge counts the same.

DFS follows one route as far as it goes before backing up to try the next. It keeps a stack, or uses recursion, which amounts to the same thing. It finds a path, but not necessarily a short one. It's the basis of many other algorithms: finding connected parts of a graph, detecting cycles, and putting tasks in an order that respects their dependencies.

With weighted edges, the fewest edges isn't the cheapest route. Edsger Dijkstra's algorithm, published in 1959, keeps a best-known distance to every node. Each step it takes the unfinished node with the smallest distance, marks it finished, and checks whether going through it makes any neighbour cheaper. Once a node is finished its distance can't improve, as long as no weight is negative, which is why negative weights are refused here.

In the sample, the cheapest way from A to E is A, C, B, D, E, costing 2 + 1 + 5 + 2 = 10, even though A, C, E uses fewer edges: that route costs 12.