Instantly share code, notes, and snippets.

# jcbozonier/gist:5424843 Created Apr 20, 2013

What would you like to do?
Generated explanation for finding the solution.
 === Finding shortest path from A to H === === Testing if goal node 'H' is cheapest discovered option === === Goal node has either not been discovered or is NOT the cheapest option! === === Lowest cost path === {'path': ['A'], 'cost': 0} === New paths to explore === [{'path': ['A', 'C'], 'cost': 2}, {'path': ['A', 'B'], 'cost': 1}] === Removed explored path === {'path': ['A'], 'cost': 0} === Remaining paths === [{'path': ['A', 'C'], 'cost': 2}, {'path': ['A', 'B'], 'cost': 1}] === Testing if goal node 'H' is cheapest discovered option === === Goal node has either not been discovered or is NOT the cheapest option! === === Lowest cost path === {'path': ['A', 'B'], 'cost': 1} === New paths to explore === [{'path': ['A', 'B', 'C'], 'cost': 2}, {'path': ['A', 'B', 'E'], 'cost': 4}, {'path': ['A', 'B', 'F'], 'cost': 7}] === Removed explored path === {'path': ['A', 'B'], 'cost': 1} === Remaining paths === [{'path': ['A', 'C'], 'cost': 2}, {'path': ['A', 'B', 'C'], 'cost': 2}, {'path': ['A', 'B', 'E'], 'cost': 4}, {'path': ['A', 'B', 'F'], 'cost': 7}] === Testing if goal node 'H' is cheapest discovered option === === Goal node has either not been discovered or is NOT the cheapest option! === === Lowest cost path === {'path': ['A', 'C'], 'cost': 2} === New paths to explore === [{'path': ['A', 'C', 'E'], 'cost': 6}, {'path': ['A', 'C', 'D'], 'cost': 4}] === Removed explored path === {'path': ['A', 'C'], 'cost': 2} === Remaining paths === [{'path': ['A', 'B', 'C'], 'cost': 2}, {'path': ['A', 'B', 'E'], 'cost': 4}, {'path': ['A', 'B', 'F'], 'cost': 7}, {'path': ['A', 'C', 'E'], 'cost': 6}, {'path': ['A', 'C', 'D'], 'cost': 4}] === Testing if goal node 'H' is cheapest discovered option === === Goal node has either not been discovered or is NOT the cheapest option! === === Lowest cost path === {'path': ['A', 'B', 'C'], 'cost': 2} === New paths to explore === [{'path': ['A', 'B', 'C', 'E'], 'cost': 6}, {'path': ['A', 'B', 'C', 'D'], 'cost': 4}] === Removed explored path === {'path': ['A', 'B', 'C'], 'cost': 2} === Remaining paths === [{'path': ['A', 'B', 'E'], 'cost': 4}, {'path': ['A', 'B', 'F'], 'cost': 7}, {'path': ['A', 'C', 'E'], 'cost': 6}, {'path': ['A', 'C', 'D'], 'cost': 4}, {'path': ['A', 'B', 'C', 'E'], 'cost': 6}, {'path': ['A', 'B', 'C', 'D'], 'cost': 4}] === Testing if goal node 'H' is cheapest discovered option === === Goal node has either not been discovered or is NOT the cheapest option! === === Lowest cost path === {'path': ['A', 'B', 'E'], 'cost': 4} === New paths to explore === [{'path': ['A', 'B', 'E', 'G'], 'cost': 6}, {'path': ['A', 'B', 'E', 'F'], 'cost': 6}] === Removed explored path === {'path': ['A', 'B', 'E'], 'cost': 4} === Remaining paths === [{'path': ['A', 'B', 'F'], 'cost': 7}, {'path': ['A', 'C', 'E'], 'cost': 6}, {'path': ['A', 'C', 'D'], 'cost': 4}, {'path': ['A', 'B', 'C', 'E'], 'cost': 6}, {'path': ['A', 'B', 'C', 'D'], 'cost': 4}, {'path': ['A', 'B', 'E', 'G'], 'cost': 6}, {'path': ['A', 'B', 'E', 'F'], 'cost': 6}] === Testing if goal node 'H' is cheapest discovered option === === Goal node has either not been discovered or is NOT the cheapest option! === === Lowest cost path === {'path': ['A', 'C', 'D'], 'cost': 4} === New paths to explore === [{'path': ['A', 'C', 'D', 'E'], 'cost': 5}, {'path': ['A', 'C', 'D', 'G'], 'cost': 8}] === Removed explored path === {'path': ['A', 'C', 'D'], 'cost': 4} === Remaining paths === [{'path': ['A', 'B', 'F'], 'cost': 7}, {'path': ['A', 'C', 'E'], 'cost': 6}, {'path': ['A', 'B', 'C', 'E'], 'cost': 6}, {'path': ['A', 'B', 'C', 'D'], 'cost': 4}, {'path': ['A', 'B', 'E', 'G'], 'cost': 6}, {'path': ['A', 'B', 'E', 'F'], 'cost': 6}, {'path': ['A', 'C', 'D', 'E'], 'cost': 5}, {'path': ['A', 'C', 'D', 'G'], 'cost': 8}] === Testing if goal node 'H' is cheapest discovered option === === Goal node has either not been discovered or is NOT the cheapest option! === === Lowest cost path === {'path': ['A', 'B', 'C', 'D'], 'cost': 4} === New paths to explore === [{'path': ['A', 'B', 'C', 'D', 'E'], 'cost': 5}, {'path': ['A', 'B', 'C', 'D', 'G'], 'cost': 8}] === Removed explored path === {'path': ['A', 'B', 'C', 'D'], 'cost': 4} === Remaining paths === [{'path': ['A', 'B', 'F'], 'cost': 7}, {'path': ['A', 'C', 'E'], 'cost': 6}, {'path': ['A', 'B', 'C', 'E'], 'cost': 6}, {'path': ['A', 'B', 'E', 'G'], 'cost': 6}, {'path': ['A', 'B', 'E', 'F'], 'cost': 6}, {'path': ['A', 'C', 'D', 'E'], 'cost': 5}, {'path': ['A', 'C', 'D', 'G'], 'cost': 8}, {'path': ['A', 'B', 'C', 'D', 'E'], 'cost': 5}, {'path': ['A', 'B', 'C', 'D', 'G'], 'cost': 8}] === Testing if goal node 'H' is cheapest discovered option === === Goal node has either not been discovered or is NOT the cheapest option! === === Lowest cost path === {'path': ['A', 'C', 'D', 'E'], 'cost': 5} === New paths to explore === [{'path': ['A', 'C', 'D', 'E', 'G'], 'cost': 7}, {'path': ['A', 'C', 'D', 'E', 'F'], 'cost': 7}] === Removed explored path === {'path': ['A', 'C', 'D', 'E'], 'cost': 5} === Remaining paths === [{'path': ['A', 'B', 'F'], 'cost': 7}, {'path': ['A', 'C', 'E'], 'cost': 6}, {'path': ['A', 'B', 'C', 'E'], 'cost': 6}, {'path': ['A', 'B', 'E', 'G'], 'cost': 6}, {'path': ['A', 'B', 'E', 'F'], 'cost': 6}, {'path': ['A', 'C', 'D', 'G'], 'cost': 8}, {'path': ['A', 'B', 'C', 'D', 'E'], 'cost': 5}, {'path': ['A', 'B', 'C', 'D', 'G'], 'cost': 8}, {'path': ['A', 'C', 'D', 'E', 'G'], 'cost': 7}, {'path': ['A', 'C', 'D', 'E', 'F'], 'cost': 7}] === Testing if goal node 'H' is cheapest discovered option === === Goal node has either not been discovered or is NOT the cheapest option! === === Lowest cost path === {'path': ['A', 'B', 'C', 'D', 'E'], 'cost': 5} === New paths to explore === [{'path': ['A', 'B', 'C', 'D', 'E', 'G'], 'cost': 7}, {'path': ['A', 'B', 'C', 'D', 'E', 'F'], 'cost': 7}] === Removed explored path === {'path': ['A', 'B', 'C', 'D', 'E'], 'cost': 5} === Remaining paths === [{'path': ['A', 'B', 'F'], 'cost': 7}, {'path': ['A', 'C', 'E'], 'cost': 6}, {'path': ['A', 'B', 'C', 'E'], 'cost': 6}, {'path': ['A', 'B', 'E', 'G'], 'cost': 6}, {'path': ['A', 'B', 'E', 'F'], 'cost': 6}, {'path': ['A', 'C', 'D', 'G'], 'cost': 8}, {'path': ['A', 'B', 'C', 'D', 'G'], 'cost': 8}, {'path': ['A', 'C', 'D', 'E', 'G'], 'cost': 7}, {'path': ['A', 'C', 'D', 'E', 'F'], 'cost': 7}, {'path': ['A', 'B', 'C', 'D', 'E', 'G'], 'cost': 7}, {'path': ['A', 'B', 'C', 'D', 'E', 'F'], 'cost': 7}] === Testing if goal node 'H' is cheapest discovered option === === Goal node has either not been discovered or is NOT the cheapest option! === === Lowest cost path === {'path': ['A', 'C', 'E'], 'cost': 6} === New paths to explore === [{'path': ['A', 'C', 'E', 'G'], 'cost': 8}, {'path': ['A', 'C', 'E', 'F'], 'cost': 8}] === Removed explored path === {'path': ['A', 'C', 'E'], 'cost': 6} === Remaining paths === [{'path': ['A', 'B', 'F'], 'cost': 7}, {'path': ['A', 'B', 'C', 'E'], 'cost': 6}, {'path': ['A', 'B', 'E', 'G'], 'cost': 6}, {'path': ['A', 'B', 'E', 'F'], 'cost': 6}, {'path': ['A', 'C', 'D', 'G'], 'cost': 8}, {'path': ['A', 'B', 'C', 'D', 'G'], 'cost': 8}, {'path': ['A', 'C', 'D', 'E', 'G'], 'cost': 7}, {'path': ['A', 'C', 'D', 'E', 'F'], 'cost': 7}, {'path': ['A', 'B', 'C', 'D', 'E', 'G'], 'cost': 7}, {'path': ['A', 'B', 'C', 'D', 'E', 'F'], 'cost': 7}, {'path': ['A', 'C', 'E', 'G'], 'cost': 8}, {'path': ['A', 'C', 'E', 'F'], 'cost': 8}] === Testing if goal node 'H' is cheapest discovered option === === Goal node has either not been discovered or is NOT the cheapest option! === === Lowest cost path === {'path': ['A', 'B', 'C', 'E'], 'cost': 6} === New paths to explore === [{'path': ['A', 'B', 'C', 'E', 'G'], 'cost': 8}, {'path': ['A', 'B', 'C', 'E', 'F'], 'cost': 8}] === Removed explored path === {'path': ['A', 'B', 'C', 'E'], 'cost': 6} === Remaining paths === [{'path': ['A', 'B', 'F'], 'cost': 7}, {'path': ['A', 'B', 'E', 'G'], 'cost': 6}, {'path': ['A', 'B', 'E', 'F'], 'cost': 6}, {'path': ['A', 'C', 'D', 'G'], 'cost': 8}, {'path': ['A', 'B', 'C', 'D', 'G'], 'cost': 8}, {'path': ['A', 'C', 'D', 'E', 'G'], 'cost': 7}, {'path': ['A', 'C', 'D', 'E', 'F'], 'cost': 7}, {'path': ['A', 'B', 'C', 'D', 'E', 'G'], 'cost': 7}, {'path': ['A', 'B', 'C', 'D', 'E', 'F'], 'cost': 7}, {'path': ['A', 'C', 'E', 'G'], 'cost': 8}, {'path': ['A', 'C', 'E', 'F'], 'cost': 8}, {'path': ['A', 'B', 'C', 'E', 'G'], 'cost': 8}, {'path': ['A', 'B', 'C', 'E', 'F'], 'cost': 8}] === Testing if goal node 'H' is cheapest discovered option === === Goal node has either not been discovered or is NOT the cheapest option! === === Lowest cost path === {'path': ['A', 'B', 'E', 'G'], 'cost': 6} === New paths to explore === [{'path': ['A', 'B', 'E', 'G', 'H'], 'cost': 20}] === Removed explored path === {'path': ['A', 'B', 'E', 'G'], 'cost': 6} === Remaining paths === [{'path': ['A', 'B', 'F'], 'cost': 7}, {'path': ['A', 'B', 'E', 'F'], 'cost': 6}, {'path': ['A', 'C', 'D', 'G'], 'cost': 8}, {'path': ['A', 'B', 'C', 'D', 'G'], 'cost': 8}, {'path': ['A', 'C', 'D', 'E', 'G'], 'cost': 7}, {'path': ['A', 'C', 'D', 'E', 'F'], 'cost': 7}, {'path': ['A', 'B', 'C', 'D', 'E', 'G'], 'cost': 7}, {'path': ['A', 'B', 'C', 'D', 'E', 'F'], 'cost': 7}, {'path': ['A', 'C', 'E', 'G'], 'cost': 8}, {'path': ['A', 'C', 'E', 'F'], 'cost': 8}, {'path': ['A', 'B', 'C', 'E', 'G'], 'cost': 8}, {'path': ['A', 'B', 'C', 'E', 'F'], 'cost': 8}, {'path': ['A', 'B', 'E', 'G', 'H'], 'cost': 20}] === Testing if goal node 'H' is cheapest discovered option === === Goal node has either not been discovered or is NOT the cheapest option! === === Lowest cost path === {'path': ['A', 'B', 'E', 'F'], 'cost': 6} === New paths to explore === [{'path': ['A', 'B', 'E', 'F', 'H'], 'cost': 17}, {'path': ['A', 'B', 'E', 'F', 'G'], 'cost': 7}] === Removed explored path === {'path': ['A', 'B', 'E', 'F'], 'cost': 6} === Remaining paths === [{'path': ['A', 'B', 'F'], 'cost': 7}, {'path': ['A', 'C', 'D', 'G'], 'cost': 8}, {'path': ['A', 'B', 'C', 'D', 'G'], 'cost': 8}, {'path': ['A', 'C', 'D', 'E', 'G'], 'cost': 7}, {'path': ['A', 'C', 'D', 'E', 'F'], 'cost': 7}, {'path': ['A', 'B', 'C', 'D', 'E', 'G'], 'cost': 7}, {'path': ['A', 'B', 'C', 'D', 'E', 'F'], 'cost': 7}, {'path': ['A', 'C', 'E', 'G'], 'cost': 8}, {'path': ['A', 'C', 'E', 'F'], 'cost': 8}, {'path': ['A', 'B', 'C', 'E', 'G'], 'cost': 8}, {'path': ['A', 'B', 'C', 'E', 'F'], 'cost': 8}, {'path': ['A', 'B', 'E', 'G', 'H'], 'cost': 20}, {'path': ['A', 'B', 'E', 'F', 'H'], 'cost': 17}, {'path': ['A', 'B', 'E', 'F', 'G'], 'cost': 7}] === Testing if goal node 'H' is cheapest discovered option === === Goal node has either not been discovered or is NOT the cheapest option! === === Lowest cost path === {'path': ['A', 'B', 'F'], 'cost': 7} === New paths to explore === [{'path': ['A', 'B', 'F', 'H'], 'cost': 18}, {'path': ['A', 'B', 'F', 'G'], 'cost': 8}] === Removed explored path === {'path': ['A', 'B', 'F'], 'cost': 7} === Remaining paths === [{'path': ['A', 'C', 'D', 'G'], 'cost': 8}, {'path': ['A', 'B', 'C', 'D', 'G'], 'cost': 8}, {'path': ['A', 'C', 'D', 'E', 'G'], 'cost': 7}, {'path': ['A', 'C', 'D', 'E', 'F'], 'cost': 7}, {'path': ['A', 'B', 'C', 'D', 'E', 'G'], 'cost': 7}, {'path': ['A', 'B', 'C', 'D', 'E', 'F'], 'cost': 7}, {'path': ['A', 'C', 'E', 'G'], 'cost': 8}, {'path': ['A', 'C', 'E', 'F'], 'cost': 8}, {'path': ['A', 'B', 'C', 'E', 'G'], 'cost': 8}, {'path': ['A', 'B', 'C', 'E', 'F'], 'cost': 8}, {'path': ['A', 'B', 'E', 'G', 'H'], 'cost': 20}, {'path': ['A', 'B', 'E', 'F', 'H'], 'cost': 17}, {'path': ['A', 'B', 'E', 'F', 'G'], 'cost': 7}, {'path': ['A', 'B', 'F', 'H'], 'cost': 18}, {'path': ['A', 'B', 'F', 'G'], 'cost': 8}] === Testing if goal node 'H' is cheapest discovered option === === Goal node has either not been discovered or is NOT the cheapest option! === === Lowest cost path === {'path': ['A', 'C', 'D', 'E', 'G'], 'cost': 7} === New paths to explore === [{'path': ['A', 'C', 'D', 'E', 'G', 'H'], 'cost': 21}] === Removed explored path === {'path': ['A', 'C', 'D', 'E', 'G'], 'cost': 7} === Remaining paths === [{'path': ['A', 'C', 'D', 'G'], 'cost': 8}, {'path': ['A', 'B', 'C', 'D', 'G'], 'cost': 8}, {'path': ['A', 'C', 'D', 'E', 'F'], 'cost': 7}, {'path': ['A', 'B', 'C', 'D', 'E', 'G'], 'cost': 7}, {'path': ['A', 'B', 'C', 'D', 'E', 'F'], 'cost': 7}, {'path': ['A', 'C', 'E', 'G'], 'cost': 8}, {'path': ['A', 'C', 'E', 'F'], 'cost': 8}, {'path': ['A', 'B', 'C', 'E', 'G'], 'cost': 8}, {'path': ['A', 'B', 'C', 'E', 'F'], 'cost': 8}, {'path': ['A', 'B', 'E', 'G', 'H'], 'cost': 20}, {'path': ['A', 'B', 'E', 'F', 'H'], 'cost': 17}, {'path': ['A', 'B', 'E', 'F', 'G'], 'cost': 7}, {'path': ['A', 'B', 'F', 'H'], 'cost': 18}, {'path': ['A', 'B', 'F', 'G'], 'cost': 8}, {'path': ['A', 'C', 'D', 'E', 'G', 'H'], 'cost': 21}] === Testing if goal node 'H' is cheapest discovered option === === Goal node has either not been discovered or is NOT the cheapest option! === === Lowest cost path === {'path': ['A', 'C', 'D', 'E', 'F'], 'cost': 7} === New paths to explore === [{'path': ['A', 'C', 'D', 'E', 'F', 'H'], 'cost': 18}, {'path': ['A', 'C', 'D', 'E', 'F', 'G'], 'cost': 8}] === Removed explored path === {'path': ['A', 'C', 'D', 'E', 'F'], 'cost': 7} === Remaining paths === [{'path': ['A', 'C', 'D', 'G'], 'cost': 8}, {'path': ['A', 'B', 'C', 'D', 'G'], 'cost': 8}, {'path': ['A', 'B', 'C', 'D', 'E', 'G'], 'cost': 7}, {'path': ['A', 'B', 'C', 'D', 'E', 'F'], 'cost': 7}, {'path': ['A', 'C', 'E', 'G'], 'cost': 8}, {'path': ['A', 'C', 'E', 'F'], 'cost': 8}, {'path': ['A', 'B', 'C', 'E', 'G'], 'cost': 8}, {'path': ['A', 'B', 'C', 'E', 'F'], 'cost': 8}, {'path': ['A', 'B', 'E', 'G', 'H'], 'cost': 20}, {'path': ['A', 'B', 'E', 'F', 'H'], 'cost': 17}, {'path': ['A', 'B', 'E', 'F', 'G'], 'cost': 7}, {'path': ['A', 'B', 'F', 'H'], 'cost': 18}, {'path': ['A', 'B', 'F', 'G'], 'cost': 8}, {'path': ['A', 'C', 'D', 'E', 'G', 'H'], 'cost': 21}, {'path': ['A', 'C', 'D', 'E', 'F', 'H'], 'cost': 18}, {'path': ['A', 'C', 'D', 'E', 'F', 'G'], 'cost': 8}] === Testing if goal node 'H' is cheapest discovered option === === Goal node has either not been discovered or is NOT the cheapest option! === === Lowest cost path === {'path': ['A', 'B', 'C', 'D', 'E', 'G'], 'cost': 7} === New paths to explore === [{'path': ['A', 'B', 'C', 'D', 'E', 'G', 'H'], 'cost': 21}] === Removed explored path === {'path': ['A', 'B', 'C', 'D', 'E', 'G'], 'cost': 7} === Remaining paths === [{'path': ['A', 'C', 'D', 'G'], 'cost': 8}, {'path': ['A', 'B', 'C', 'D', 'G'], 'cost': 8}, {'path': ['A', 'B', 'C', 'D', 'E', 'F'], 'cost': 7}, {'path': ['A', 'C', 'E', 'G'], 'cost': 8}, {'path': ['A', 'C', 'E', 'F'], 'cost': 8}, {'path': ['A', 'B', 'C', 'E', 'G'], 'cost': 8}, {'path': ['A', 'B', 'C', 'E', 'F'], 'cost': 8}, {'path': ['A', 'B', 'E', 'G', 'H'], 'cost': 20}, {'path': ['A', 'B', 'E', 'F', 'H'], 'cost': 17}, {'path': ['A', 'B', 'E', 'F', 'G'], 'cost': 7}, {'path': ['A', 'B', 'F', 'H'], 'cost': 18}, {'path': ['A', 'B', 'F', 'G'], 'cost': 8}, {'path': ['A', 'C', 'D', 'E', 'G', 'H'], 'cost': 21}, {'path': ['A', 'C', 'D', 'E', 'F', 'H'], 'cost': 18}, {'path': ['A', 'C', 'D', 'E', 'F', 'G'], 'cost': 8}, {'path': ['A', 'B', 'C', 'D', 'E', 'G', 'H'], 'cost': 21}] === Testing if goal node 'H' is cheapest discovered option === === Goal node has either not been discovered or is NOT the cheapest option! === === Lowest cost path === {'path': ['A', 'B', 'C', 'D', 'E', 'F'], 'cost': 7} === New paths to explore === [{'path': ['A', 'B', 'C', 'D', 'E', 'F', 'H'], 'cost': 18}, {'path': ['A', 'B', 'C', 'D', 'E', 'F', 'G'], 'cost': 8}] === Removed explored path === {'path': ['A', 'B', 'C', 'D', 'E', 'F'], 'cost': 7} === Remaining paths === [{'path': ['A', 'C', 'D', 'G'], 'cost': 8}, {'path': ['A', 'B', 'C', 'D', 'G'], 'cost': 8}, {'path': ['A', 'C', 'E', 'G'], 'cost': 8}, {'path': ['A', 'C', 'E', 'F'], 'cost': 8}, {'path': ['A', 'B', 'C', 'E', 'G'], 'cost': 8}, {'path': ['A', 'B', 'C', 'E', 'F'], 'cost': 8}, {'path': ['A', 'B', 'E', 'G', 'H'], 'cost': 20}, {'path': ['A', 'B', 'E', 'F', 'H'], 'cost': 17}, {'path': ['A', 'B', 'E', 'F', 'G'], 'cost': 7}, {'path': ['A', 'B', 'F', 'H'], 'cost': 18}, {'path': ['A', 'B', 'F', 'G'], 'cost': 8}, {'path': ['A', 'C', 'D', 'E', 'G', 'H'], 'cost': 21}, {'path': ['A', 'C', 'D', 'E', 'F', 'H'], 'cost': 18}, {'path': ['A', 'C', 'D', 'E', 'F', 'G'], 'cost': 8}, {'path': ['A', 'B', 'C', 'D', 'E', 'G', 'H'], 'cost': 21}, {'path': ['A', 'B', 'C', 'D', 'E', 'F', 'H'], 'cost': 18}, {'path': ['A', 'B', 'C', 'D', 'E', 'F', 'G'], 'cost': 8}] === Testing if goal node 'H' is cheapest discovered option === === Goal node has either not been discovered or is NOT the cheapest option! === === Lowest cost path === {'path': ['A', 'B', 'E', 'F', 'G'], 'cost': 7} === New paths to explore === [{'path': ['A', 'B', 'E', 'F', 'G', 'H'], 'cost': 21}] === Removed explored path === {'path': ['A', 'B', 'E', 'F', 'G'], 'cost': 7} === Remaining paths === [{'path': ['A', 'C', 'D', 'G'], 'cost': 8}, {'path': ['A', 'B', 'C', 'D', 'G'], 'cost': 8}, {'path': ['A', 'C', 'E', 'G'], 'cost': 8}, {'path': ['A', 'C', 'E', 'F'], 'cost': 8}, {'path': ['A', 'B', 'C', 'E', 'G'], 'cost': 8}, {'path': ['A', 'B', 'C', 'E', 'F'], 'cost': 8}, {'path': ['A', 'B', 'E', 'G', 'H'], 'cost': 20}, {'path': ['A', 'B', 'E', 'F', 'H'], 'cost': 17}, {'path': ['A', 'B', 'F', 'H'], 'cost': 18}, {'path': ['A', 'B', 'F', 'G'], 'cost': 8}, {'path': ['A', 'C', 'D', 'E', 'G', 'H'], 'cost': 21}, {'path': ['A', 'C', 'D', 'E', 'F', 'H'], 'cost': 18}, {'path': ['A', 'C', 'D', 'E', 'F', 'G'], 'cost': 8}, {'path': ['A', 'B', 'C', 'D', 'E', 'G', 'H'], 'cost': 21}, {'path': ['A', 'B', 'C', 'D', 'E', 'F', 'H'], 'cost': 18}, {'path': ['A', 'B', 'C', 'D', 'E', 'F', 'G'], 'cost': 8}, {'path': ['A', 'B', 'E', 'F', 'G', 'H'], 'cost': 21}] === Testing if goal node 'H' is cheapest discovered option === === Goal node has either not been discovered or is NOT the cheapest option! === === Lowest cost path === {'path': ['A', 'C', 'D', 'G'], 'cost': 8} === New paths to explore === [{'path': ['A', 'C', 'D', 'G', 'H'], 'cost': 22}] === Removed explored path === {'path': ['A', 'C', 'D', 'G'], 'cost': 8} === Remaining paths === [{'path': ['A', 'B', 'C', 'D', 'G'], 'cost': 8}, {'path': ['A', 'C', 'E', 'G'], 'cost': 8}, {'path': ['A', 'C', 'E', 'F'], 'cost': 8}, {'path': ['A', 'B', 'C', 'E', 'G'], 'cost': 8}, {'path': ['A', 'B', 'C', 'E', 'F'], 'cost': 8}, {'path': ['A', 'B', 'E', 'G', 'H'], 'cost': 20}, {'path': ['A', 'B', 'E', 'F', 'H'], 'cost': 17}, {'path': ['A', 'B', 'F', 'H'], 'cost': 18}, {'path': ['A', 'B', 'F', 'G'], 'cost': 8}, {'path': ['A', 'C', 'D', 'E', 'G', 'H'], 'cost': 21}, {'path': ['A', 'C', 'D', 'E', 'F', 'H'], 'cost': 18}, {'path': ['A', 'C', 'D', 'E', 'F', 'G'], 'cost': 8}, {'path': ['A', 'B', 'C', 'D', 'E', 'G', 'H'], 'cost': 21}, {'path': ['A', 'B', 'C', 'D', 'E', 'F', 'H'], 'cost': 18}, {'path': ['A', 'B', 'C', 'D', 'E', 'F', 'G'], 'cost': 8}, {'path': ['A', 'B', 'E', 'F', 'G', 'H'], 'cost': 21}, {'path': ['A', 'C', 'D', 'G', 'H'], 'cost': 22}] === Testing if goal node 'H' is cheapest discovered option === === Goal node has either not been discovered or is NOT the cheapest option! === === Lowest cost path === {'path': ['A', 'B', 'C', 'D', 'G'], 'cost': 8} === New paths to explore === [{'path': ['A', 'B', 'C', 'D', 'G', 'H'], 'cost': 22}] === Removed explored path === {'path': ['A', 'B', 'C', 'D', 'G'], 'cost': 8} === Remaining paths === [{'path': ['A', 'C', 'E', 'G'], 'cost': 8}, {'path': ['A', 'C', 'E', 'F'], 'cost': 8}, {'path': ['A', 'B', 'C', 'E', 'G'], 'cost': 8}, {'path': ['A', 'B', 'C', 'E', 'F'], 'cost': 8}, {'path': ['A', 'B', 'E', 'G', 'H'], 'cost': 20}, {'path': ['A', 'B', 'E', 'F', 'H'], 'cost': 17}, {'path': ['A', 'B', 'F', 'H'], 'cost': 18}, {'path': ['A', 'B', 'F', 'G'], 'cost': 8}, {'path': ['A', 'C', 'D', 'E', 'G', 'H'], 'cost': 21}, {'path': ['A', 'C', 'D', 'E', 'F', 'H'], 'cost': 18}, {'path': ['A', 'C', 'D', 'E', 'F', 'G'], 'cost': 8}, {'path': ['A', 'B', 'C', 'D', 'E', 'G', 'H'], 'cost': 21}, {'path': ['A', 'B', 'C', 'D', 'E', 'F', 'H'], 'cost': 18}, {'path': ['A', 'B', 'C', 'D', 'E', 'F', 'G'], 'cost': 8}, {'path': ['A', 'B', 'E', 'F', 'G', 'H'], 'cost': 21}, {'path': ['A', 'C', 'D', 'G', 'H'], 'cost': 22}, {'path': ['A', 'B', 'C', 'D', 'G', 'H'], 'cost': 22}] === Testing if goal node 'H' is cheapest discovered option === === Goal node has either not been discovered or is NOT the cheapest option! === === Lowest cost path === {'path': ['A', 'C', 'E', 'G'], 'cost': 8} === New paths to explore === [{'path': ['A', 'C', 'E', 'G', 'H'], 'cost': 22}] === Removed explored path === {'path': ['A', 'C', 'E', 'G'], 'cost': 8} === Remaining paths === [{'path': ['A', 'C', 'E', 'F'], 'cost': 8}, {'path': ['A', 'B', 'C', 'E', 'G'], 'cost': 8}, {'path': ['A', 'B', 'C', 'E', 'F'], 'cost': 8}, {'path': ['A', 'B', 'E', 'G', 'H'], 'cost': 20}, {'path': ['A', 'B', 'E', 'F', 'H'], 'cost': 17}, {'path': ['A', 'B', 'F', 'H'], 'cost': 18}, {'path': ['A', 'B', 'F', 'G'], 'cost': 8}, {'path': ['A', 'C', 'D', 'E', 'G', 'H'], 'cost': 21}, {'path': ['A', 'C', 'D', 'E', 'F', 'H'], 'cost': 18}, {'path': ['A', 'C', 'D', 'E', 'F', 'G'], 'cost': 8}, {'path': ['A', 'B', 'C', 'D', 'E', 'G', 'H'], 'cost': 21}, {'path': ['A', 'B', 'C', 'D', 'E', 'F', 'H'], 'cost': 18}, {'path': ['A', 'B', 'C', 'D', 'E', 'F', 'G'], 'cost': 8}, {'path': ['A', 'B', 'E', 'F', 'G', 'H'], 'cost': 21}, {'path': ['A', 'C', 'D', 'G', 'H'], 'cost': 22}, {'path': ['A', 'B', 'C', 'D', 'G', 'H'], 'cost': 22}, {'path': ['A', 'C', 'E', 'G', 'H'], 'cost': 22}] === Testing if goal node 'H' is cheapest discovered option === === Goal node has either not been discovered or is NOT the cheapest option! === === Lowest cost path === {'path': ['A', 'C', 'E', 'F'], 'cost': 8} === New paths to explore === [{'path': ['A', 'C', 'E', 'F', 'H'], 'cost': 19}, {'path': ['A', 'C', 'E', 'F', 'G'], 'cost': 9}] === Removed explored path === {'path': ['A', 'C', 'E', 'F'], 'cost': 8} === Remaining paths === [{'path': ['A', 'B', 'C', 'E', 'G'], 'cost': 8}, {'path': ['A', 'B', 'C', 'E', 'F'], 'cost': 8}, {'path': ['A', 'B', 'E', 'G', 'H'], 'cost': 20}, {'path': ['A', 'B', 'E', 'F', 'H'], 'cost': 17}, {'path': ['A', 'B', 'F', 'H'], 'cost': 18}, {'path': ['A', 'B', 'F', 'G'], 'cost': 8}, {'path': ['A', 'C', 'D', 'E', 'G', 'H'], 'cost': 21}, {'path': ['A', 'C', 'D', 'E', 'F', 'H'], 'cost': 18}, {'path': ['A', 'C', 'D', 'E', 'F', 'G'], 'cost': 8}, {'path': ['A', 'B', 'C', 'D', 'E', 'G', 'H'], 'cost': 21}, {'path': ['A', 'B', 'C', 'D', 'E', 'F', 'H'], 'cost': 18}, {'path': ['A', 'B', 'C', 'D', 'E', 'F', 'G'], 'cost': 8}, {'path': ['A', 'B', 'E', 'F', 'G', 'H'], 'cost': 21}, {'path': ['A', 'C', 'D', 'G', 'H'], 'cost': 22}, {'path': ['A', 'B', 'C', 'D', 'G', 'H'], 'cost': 22}, {'path': ['A', 'C', 'E', 'G', 'H'], 'cost': 22}, {'path': ['A', 'C', 'E', 'F', 'H'], 'cost': 19}, {'path': ['A', 'C', 'E', 'F', 'G'], 'cost': 9}] === Testing if goal node 'H' is cheapest discovered option === === Goal node has either not been discovered or is NOT the cheapest option! === === Lowest cost path === {'path': ['A', 'B', 'C', 'E', 'G'], 'cost': 8} === New paths to explore === [{'path': ['A', 'B', 'C', 'E', 'G', 'H'], 'cost': 22}] === Removed explored path === {'path': ['A', 'B', 'C', 'E', 'G'], 'cost': 8} === Remaining paths === [{'path': ['A', 'B', 'C', 'E', 'F'], 'cost': 8}, {'path': ['A', 'B', 'E', 'G', 'H'], 'cost': 20}, {'path': ['A', 'B', 'E', 'F', 'H'], 'cost': 17}, {'path': ['A', 'B', 'F', 'H'], 'cost': 18}, {'path': ['A', 'B', 'F', 'G'], 'cost': 8}, {'path': ['A', 'C', 'D', 'E', 'G', 'H'], 'cost': 21}, {'path': ['A', 'C', 'D', 'E', 'F', 'H'], 'cost': 18}, {'path': ['A', 'C', 'D', 'E', 'F', 'G'], 'cost': 8}, {'path': ['A', 'B', 'C', 'D', 'E', 'G', 'H'], 'cost': 21}, {'path': ['A', 'B', 'C', 'D', 'E', 'F', 'H'], 'cost': 18}, {'path': ['A', 'B', 'C', 'D', 'E', 'F', 'G'], 'cost': 8}, {'path': ['A', 'B', 'E', 'F', 'G', 'H'], 'cost': 21}, {'path': ['A', 'C', 'D', 'G', 'H'], 'cost': 22}, {'path': ['A', 'B', 'C', 'D', 'G', 'H'], 'cost': 22}, {'path': ['A', 'C', 'E', 'G', 'H'], 'cost': 22}, {'path': ['A', 'C', 'E', 'F', 'H'], 'cost': 19}, {'path': ['A', 'C', 'E', 'F', 'G'], 'cost': 9}, {'path': ['A', 'B', 'C', 'E', 'G', 'H'], 'cost': 22}] === Testing if goal node 'H' is cheapest discovered option === === Goal node has either not been discovered or is NOT the cheapest option! === === Lowest cost path === {'path': ['A', 'B', 'C', 'E', 'F'], 'cost': 8} === New paths to explore === [{'path': ['A', 'B', 'C', 'E', 'F', 'H'], 'cost': 19}, {'path': ['A', 'B', 'C', 'E', 'F', 'G'], 'cost': 9}] === Removed explored path === {'path': ['A', 'B', 'C', 'E', 'F'], 'cost': 8} === Remaining paths === [{'path': ['A', 'B', 'E', 'G', 'H'], 'cost': 20}, {'path': ['A', 'B', 'E', 'F', 'H'], 'cost': 17}, {'path': ['A', 'B', 'F', 'H'], 'cost': 18}, {'path': ['A', 'B', 'F', 'G'], 'cost': 8}, {'path': ['A', 'C', 'D', 'E', 'G', 'H'], 'cost': 21}, {'path': ['A', 'C', 'D', 'E', 'F', 'H'], 'cost': 18}, {'path': ['A', 'C', 'D', 'E', 'F', 'G'], 'cost': 8}, {'path': ['A', 'B', 'C', 'D', 'E', 'G', 'H'], 'cost': 21}, {'path': ['A', 'B', 'C', 'D', 'E', 'F', 'H'], 'cost': 18}, {'path': ['A', 'B', 'C', 'D', 'E', 'F', 'G'], 'cost': 8}, {'path': ['A', 'B', 'E', 'F', 'G', 'H'], 'cost': 21}, {'path': ['A', 'C', 'D', 'G', 'H'], 'cost': 22}, {'path': ['A', 'B', 'C', 'D', 'G', 'H'], 'cost': 22}, {'path': ['A', 'C', 'E', 'G', 'H'], 'cost': 22}, {'path': ['A', 'C', 'E', 'F', 'H'], 'cost': 19}, {'path': ['A', 'C', 'E', 'F', 'G'], 'cost': 9}, {'path': ['A', 'B', 'C', 'E', 'G', 'H'], 'cost': 22}, {'path': ['A', 'B', 'C', 'E', 'F', 'H'], 'cost': 19}, {'path': ['A', 'B', 'C', 'E', 'F', 'G'], 'cost': 9}] === Testing if goal node 'H' is cheapest discovered option === === Goal node has either not been discovered or is NOT the cheapest option! === === Lowest cost path === {'path': ['A', 'B', 'F', 'G'], 'cost': 8} === New paths to explore === [{'path': ['A', 'B', 'F', 'G', 'H'], 'cost': 22}] === Removed explored path === {'path': ['A', 'B', 'F', 'G'], 'cost': 8} === Remaining paths === [{'path': ['A', 'B', 'E', 'G', 'H'], 'cost': 20}, {'path': ['A', 'B', 'E', 'F', 'H'], 'cost': 17}, {'path': ['A', 'B', 'F', 'H'], 'cost': 18}, {'path': ['A', 'C', 'D', 'E', 'G', 'H'], 'cost': 21}, {'path': ['A', 'C', 'D', 'E', 'F', 'H'], 'cost': 18}, {'path': ['A', 'C', 'D', 'E', 'F', 'G'], 'cost': 8}, {'path': ['A', 'B', 'C', 'D', 'E', 'G', 'H'], 'cost': 21}, {'path': ['A', 'B', 'C', 'D', 'E', 'F', 'H'], 'cost': 18}, {'path': ['A', 'B', 'C', 'D', 'E', 'F', 'G'], 'cost': 8}, {'path': ['A', 'B', 'E', 'F', 'G', 'H'], 'cost': 21}, {'path': ['A', 'C', 'D', 'G', 'H'], 'cost': 22}, {'path': ['A', 'B', 'C', 'D', 'G', 'H'], 'cost': 22}, {'path': ['A', 'C', 'E', 'G', 'H'], 'cost': 22}, {'path': ['A', 'C', 'E', 'F', 'H'], 'cost': 19}, {'path': ['A', 'C', 'E', 'F', 'G'], 'cost': 9}, {'path': ['A', 'B', 'C', 'E', 'G', 'H'], 'cost': 22}, {'path': ['A', 'B', 'C', 'E', 'F', 'H'], 'cost': 19}, {'path': ['A', 'B', 'C', 'E', 'F', 'G'], 'cost': 9}, {'path': ['A', 'B', 'F', 'G', 'H'], 'cost': 22}] === Testing if goal node 'H' is cheapest discovered option === === Goal node has either not been discovered or is NOT the cheapest option! === === Lowest cost path === {'path': ['A', 'C', 'D', 'E', 'F', 'G'], 'cost': 8} === New paths to explore === [{'path': ['A', 'C', 'D', 'E', 'F', 'G', 'H'], 'cost': 22}] === Removed explored path === {'path': ['A', 'C', 'D', 'E', 'F', 'G'], 'cost': 8} === Remaining paths === [{'path': ['A', 'B', 'E', 'G', 'H'], 'cost': 20}, {'path': ['A', 'B', 'E', 'F', 'H'], 'cost': 17}, {'path': ['A', 'B', 'F', 'H'], 'cost': 18}, {'path': ['A', 'C', 'D', 'E', 'G', 'H'], 'cost': 21}, {'path': ['A', 'C', 'D', 'E', 'F', 'H'], 'cost': 18}, {'path': ['A', 'B', 'C', 'D', 'E', 'G', 'H'], 'cost': 21}, {'path': ['A', 'B', 'C', 'D', 'E', 'F', 'H'], 'cost': 18}, {'path': ['A', 'B', 'C', 'D', 'E', 'F', 'G'], 'cost': 8}, {'path': ['A', 'B', 'E', 'F', 'G', 'H'], 'cost': 21}, {'path': ['A', 'C', 'D', 'G', 'H'], 'cost': 22}, {'path': ['A', 'B', 'C', 'D', 'G', 'H'], 'cost': 22}, {'path': ['A', 'C', 'E', 'G', 'H'], 'cost': 22}, {'path': ['A', 'C', 'E', 'F', 'H'], 'cost': 19}, {'path': ['A', 'C', 'E', 'F', 'G'], 'cost': 9}, {'path': ['A', 'B', 'C', 'E', 'G', 'H'], 'cost': 22}, {'path': ['A', 'B', 'C', 'E', 'F', 'H'], 'cost': 19}, {'path': ['A', 'B', 'C', 'E', 'F', 'G'], 'cost': 9}, {'path': ['A', 'B', 'F', 'G', 'H'], 'cost': 22}, {'path': ['A', 'C', 'D', 'E', 'F', 'G', 'H'], 'cost': 22}] === Testing if goal node 'H' is cheapest discovered option === === Goal node has either not been discovered or is NOT the cheapest option! === === Lowest cost path === {'path': ['A', 'B', 'C', 'D', 'E', 'F', 'G'], 'cost': 8} === New paths to explore === [{'path': ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H'], 'cost': 22}] === Removed explored path === {'path': ['A', 'B', 'C', 'D', 'E', 'F', 'G'], 'cost': 8} === Remaining paths === [{'path': ['A', 'B', 'E', 'G', 'H'], 'cost': 20}, {'path': ['A', 'B', 'E', 'F', 'H'], 'cost': 17}, {'path': ['A', 'B', 'F', 'H'], 'cost': 18}, {'path': ['A', 'C', 'D', 'E', 'G', 'H'], 'cost': 21}, {'path': ['A', 'C', 'D', 'E', 'F', 'H'], 'cost': 18}, {'path': ['A', 'B', 'C', 'D', 'E', 'G', 'H'], 'cost': 21}, {'path': ['A', 'B', 'C', 'D', 'E', 'F', 'H'], 'cost': 18}, {'path': ['A', 'B', 'E', 'F', 'G', 'H'], 'cost': 21}, {'path': ['A', 'C', 'D', 'G', 'H'], 'cost': 22}, {'path': ['A', 'B', 'C', 'D', 'G', 'H'], 'cost': 22}, {'path': ['A', 'C', 'E', 'G', 'H'], 'cost': 22}, {'path': ['A', 'C', 'E', 'F', 'H'], 'cost': 19}, {'path': ['A', 'C', 'E', 'F', 'G'], 'cost': 9}, {'path': ['A', 'B', 'C', 'E', 'G', 'H'], 'cost': 22}, {'path': ['A', 'B', 'C', 'E', 'F', 'H'], 'cost': 19}, {'path': ['A', 'B', 'C', 'E', 'F', 'G'], 'cost': 9}, {'path': ['A', 'B', 'F', 'G', 'H'], 'cost': 22}, {'path': ['A', 'C', 'D', 'E', 'F', 'G', 'H'], 'cost': 22}, {'path': ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H'], 'cost': 22}] === Testing if goal node 'H' is cheapest discovered option === === Goal node has either not been discovered or is NOT the cheapest option! === === Lowest cost path === {'path': ['A', 'C', 'E', 'F', 'G'], 'cost': 9} === New paths to explore === [{'path': ['A', 'C', 'E', 'F', 'G', 'H'], 'cost': 23}] === Removed explored path === {'path': ['A', 'C', 'E', 'F', 'G'], 'cost': 9} === Remaining paths === [{'path': ['A', 'B', 'E', 'G', 'H'], 'cost': 20}, {'path': ['A', 'B', 'E', 'F', 'H'], 'cost': 17}, {'path': ['A', 'B', 'F', 'H'], 'cost': 18}, {'path': ['A', 'C', 'D', 'E', 'G', 'H'], 'cost': 21}, {'path': ['A', 'C', 'D', 'E', 'F', 'H'], 'cost': 18}, {'path': ['A', 'B', 'C', 'D', 'E', 'G', 'H'], 'cost': 21}, {'path': ['A', 'B', 'C', 'D', 'E', 'F', 'H'], 'cost': 18}, {'path': ['A', 'B', 'E', 'F', 'G', 'H'], 'cost': 21}, {'path': ['A', 'C', 'D', 'G', 'H'], 'cost': 22}, {'path': ['A', 'B', 'C', 'D', 'G', 'H'], 'cost': 22}, {'path': ['A', 'C', 'E', 'G', 'H'], 'cost': 22}, {'path': ['A', 'C', 'E', 'F', 'H'], 'cost': 19}, {'path': ['A', 'B', 'C', 'E', 'G', 'H'], 'cost': 22}, {'path': ['A', 'B', 'C', 'E', 'F', 'H'], 'cost': 19}, {'path': ['A', 'B', 'C', 'E', 'F', 'G'], 'cost': 9}, {'path': ['A', 'B', 'F', 'G', 'H'], 'cost': 22}, {'path': ['A', 'C', 'D', 'E', 'F', 'G', 'H'], 'cost': 22}, {'path': ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H'], 'cost': 22}, {'path': ['A', 'C', 'E', 'F', 'G', 'H'], 'cost': 23}] === Testing if goal node 'H' is cheapest discovered option === === Goal node has either not been discovered or is NOT the cheapest option! === === Lowest cost path === {'path': ['A', 'B', 'C', 'E', 'F', 'G'], 'cost': 9} === New paths to explore === [{'path': ['A', 'B', 'C', 'E', 'F', 'G', 'H'], 'cost': 23}] === Removed explored path === {'path': ['A', 'B', 'C', 'E', 'F', 'G'], 'cost': 9} === Remaining paths === [{'path': ['A', 'B', 'E', 'G', 'H'], 'cost': 20}, {'path': ['A', 'B', 'E', 'F', 'H'], 'cost': 17}, {'path': ['A', 'B', 'F', 'H'], 'cost': 18}, {'path': ['A', 'C', 'D', 'E', 'G', 'H'], 'cost': 21}, {'path': ['A', 'C', 'D', 'E', 'F', 'H'], 'cost': 18}, {'path': ['A', 'B', 'C', 'D', 'E', 'G', 'H'], 'cost': 21}, {'path': ['A', 'B', 'C', 'D', 'E', 'F', 'H'], 'cost': 18}, {'path': ['A', 'B', 'E', 'F', 'G', 'H'], 'cost': 21}, {'path': ['A', 'C', 'D', 'G', 'H'], 'cost': 22}, {'path': ['A', 'B', 'C', 'D', 'G', 'H'], 'cost': 22}, {'path': ['A', 'C', 'E', 'G', 'H'], 'cost': 22}, {'path': ['A', 'C', 'E', 'F', 'H'], 'cost': 19}, {'path': ['A', 'B', 'C', 'E', 'G', 'H'], 'cost': 22}, {'path': ['A', 'B', 'C', 'E', 'F', 'H'], 'cost': 19}, {'path': ['A', 'B', 'F', 'G', 'H'], 'cost': 22}, {'path': ['A', 'C', 'D', 'E', 'F', 'G', 'H'], 'cost': 22}, {'path': ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H'], 'cost': 22}, {'path': ['A', 'C', 'E', 'F', 'G', 'H'], 'cost': 23}, {'path': ['A', 'B', 'C', 'E', 'F', 'G', 'H'], 'cost': 23}] === Testing if goal node 'H' is cheapest discovered option === === Goal node is cheapest option! === === Solution found! === {'path': ['A', 'B', 'E', 'F', 'H'], 'cost': 17}