StringMash.com

Graph search: BFS, DFS and Dijkstra

Your graph, searched one step at a time, and drawn.

42 characters
Updates as you type
Visit orderA → B → C → D → E
Path to EA → C → E

The graph is drawn below

Show the steps
42158102A1B2C3D4E5
  1. Put A in the queue.
  2. Visit A. Queue its unseen neighbors B, C. Queue: B C.
  3. Visit B. Queue its unseen neighbors D. Queue: C D.
  4. Visit C. Queue its unseen neighbors E. Queue: D E.
  5. Visit D. No new neighbors. Queue: E.
  6. Visit E. No new neighbors. Queue: empty.
  7. Breadth-first search finds a path with the fewest edges: 2.

Using it

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 you typed. 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 neighbors, they are taken in alphabetical order, the usual rule in class, so your answer matches a worked solution that follows it.

Breadth-first search

BFS visits the start, then all its neighbors, 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.

Depth-first search

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.

Dijkstra's algorithm

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 neighbor 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. With an end node set, the search stops once that node is finished. Nodes it hadn't finished by then are marked not finalized.

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.

In the classroom

Ages 13 and up, about 30 minutes. Draw a small map of the school on the board as dots and lines, with walking times on the lines. Pupils find the quickest route from one room to another by hand, then type the same graph in here and compare their answer with Dijkstra's.

Take it further: run breadth-first search on the same map and ask why it finds the route with the fewest corridors rather than the quickest one.

Questions

Which is better, BFS or DFS?

BFS for the shortest path when edges are unweighted; DFS when you need to explore everything or follow structure, and it uses less memory on wide graphs.

Why is my visit order different from my textbook's?

Neighbors can be taken in any order. This page uses alphabetical order; a textbook may use the order the edges were listed.

What about A*?

A* is Dijkstra's algorithm with a guess of the distance left added to each node's priority. It needs positions to make that guess, so it isn't offered for typed graphs here.

Sources

Added . Last updated and reviewed . What's new