An adjacency list
This graph has five vertices. In Java it is stored as an adjacency list. A Map links each vertex to the list of its neighbors. It is undirected: each edge is added in both directions.
This graph has five vertices. In Java it is stored as an adjacency list.
A Map links each vertex to the list of its neighbors.
It is undirected: each edge is added in both directions.
This graph has five vertices. In Java it is stored as an adjacency list. A Map links each vertex to the list of its neighbors. It is undirected: each edge is added in both directions.
BFS uses two structures: a Set of visited vertices and a queue of pending ones.
A is marked as visited on enqueue, not on dequeue.
BFS uses two structures: a Set of visited vertices and a queue of pending ones. A is marked as visited on enqueue, not on dequeue.
The queue hands over A, the first one in, and it joins the visit order.
Its neighbors B and C are marked and enqueued: they are layer 1.
The queue hands over A, the first one in, and it joins the visit order. Its neighbors B and C are marked and enqueued: they are layer 1.
B leaves and enqueues D. When C leaves, D is already visited: it never enters twice.
Then D enqueues E. BFS explores layer by layer: 1 hop, 2 hops, 3 hops.
That is why BFS finds the path with the fewest edges.
B leaves and enqueues D. When C leaves, D is already visited: it never enters twice. Then D enqueues E. BFS explores layer by layer: 1 hop, 2 hops, 3 hops. That is why BFS finds the path with the fewest edges.
Now every edge has a weight: kilometers, minutes or cost.
For BFS, the path from A to B is the direct edge: 1 hop, but it costs 4.
Through A β C β B there are more hops, yet it costs 2 + 1 = 3. Fewer edges is not cheapest.
Now every edge has a weight: kilometers, minutes or cost. For BFS, the path from A to B is the direct edge: 1 hop, but it costs 4. Through A β C β B there are more hops, yet it costs 2 + 1 = 3. Fewer edges is not cheapest.
Dijkstra uses a priority queue: the cheapest pending vertex always comes out first.
From A, B is at 4 and C is at 2. C comes out: it is the cheapest.
Relaxing: through C, B costs 2 + 1 = 3, less than 4. Its distance is updated.
Dijkstra uses a priority queue: the cheapest pending vertex always comes out first. From A, B is at 4 and C is at 2. C comes out: it is the cheapest. Relaxing: through C, B costs 2 + 1 = 3, less than 4. Its distance is updated.
B comes out at 3: through B, D costs 3 + 5 = 8, better than 10. Relaxed again.
D comes out at 8 and E ends at 8 + 3 = 11. Each processed vertex is final.
B comes out at 3: through B, D costs 3 + 5 = 8, better than 10. Relaxed again. D comes out at 8 and E ends at 8 + 3 = 11. Each processed vertex is final.
The result is the shortest path from A to every vertex.
BFS counts edges; Dijkstra adds weights. Dijkstra does not work with negative weights.
The result is the shortest path from A to every vertex. BFS counts edges; Dijkstra adds weights. Dijkstra does not work with negative weights.