Finding how far it is from O'Neill to Bridgeport __________________________ Heap: 1 - O'Neill at t=0 __________________________ remove top and process O'Neill at t=0 leads to: Grand island at t=111 - new entry and Valentine at t=105 - new entry __________________________ Heap: 1 - Valentine at t=105 2 - Grand island at t=111 __________________________ remove top and process Valentine at t=105 leads to O'Neill at t=210 - already processed and Chadron at t=242 - new entry and Thedford at t=171 - new entry __________________________ Heap: 1 - Grand island at t=111 2 - Thedford at t=171 3 - Chadron at t=242 __________________________ remove top and process Grand island at t=111 leads to: O'Neill at t=222 - already processed and Thedford at t=256 - already know better and North Platte at t=251 - new entry __________________________ Heap: 1 - Thedford at t=171 2 - Chadron at t=242 3 - North Platte at t=251 __________________________ remove top and process Thedford at t=171 leads to: Grand Island at t=316 - already know better and North Platte at t=235 - an improvement and Valentine at t=247 - already processed and Alliance at t=295 - new entry __________________________ Heap: 1 - North Platte at t=235 2 - Chadron at t=242 3 - Alliance at t=295 __________________________ remove top and process North Platte at t=235 leads to: Grand Island at t=375 - already proecssed and Thedford at t=299 - already processed and Ogallala at t=286 - new entry __________________________ Heap: 1 - Chadron at t=242 2 - Ogallala at t=286 3 - Alliance at t=295 __________________________ remove top and process Chadron at t=242 leads to: Valentine at t=379 - already processed and Alliance at t=296 - already know better __________________________ Heap: 1 - Ogallala at t=286 2 - Alliance at t=295 __________________________ remove top and process Ogallala at t=286 leads to: North Platte at t=337 - already processed and Sidney at t=353 - new entry and Bridgeport at t=373 - new entry __________________________ Heap: 1 - Alliance at t=295 2 - Sidney at t=353 3 - Bridgeport at t=373 __________________________ remove top and process Alliance at t=295 leads to: Thedford at t=419 - already processed and Chadron at t=249 - already processed and Bridgeport at t=333 - an improvement __________________________ Heap: 1 - Bridgeport at t=333 2 - Sidney at t=353 __________________________ remove top and process Bridgeport at t=333 This is our destination. Could stop now but we'll continue leads to: Alliance at t=371 - already processed and Scotts Bluff at t=366 - new entry and Sidney at t=374 - already know better and Ogallala at t=420 - already know better __________________________ Heap: 1 - Sidney at t=353 2 - Scotts Bluff at t=366 __________________________ remove top and process Sidney at t=353 leads to: Kimball at t=393 - new entry and Bridgeport at t=394 - already processed and Ogallala at t=420 - already processed __________________________ Heap: 1 - Scotts Bluff at t=366 2 - Kimball at t=393 __________________________ remove top and process Scotts Bluff at t=366 leads to: Kimball at t=419 - already know better and Bridgeport at t=399 - already processed __________________________ Heap: 1 - Kimball at t=393 __________________________ remove top and process Kimball at t=393 leads to: Sidney at t=433 - already processed and Scotts Bluff at t=464 - already processed __________________________ Heap: __________________________ The heap is empty, so we have finished, and we know how far every town in Nebraska is from O'Neill by the shortest route.