public
Last active

Djikstra's Shortest Path algorithm in Python

  • Download Gist
gistfile1.py
Python
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52
import sys
 
def something_reaches_goal(paths, goal_node):
cheapest_path = sys.maxint
for path in paths:
if path["cost"] <= cheapest_path:
cheapest_path = path["cost"]
for path in paths:
if goal_node in path["path"] and cheapest_path == path["cost"]:
return True
return False
 
def get_lowest_cost_path(paths):
lowest_cost_path = paths[0]
for path in paths:
if lowest_cost_path["cost"] > path["cost"]:
lowest_cost_path = path
return lowest_cost_path
 
def get_nodes_and_costs(graph, path):
last_node = path["path"][-1]
if not last_node in graph:
return []
next_nodes = graph[last_node]
next_paths = []
for node in next_nodes:
if node == last_node:
continue
new_path = []
new_path.extend(path["path"])
new_path.append(node)
next_paths.append({"path": new_path, "cost": path["cost"] + next_nodes[node]})
return next_paths
 
def get_path_that_reaches_goal(paths, goal_node):
cheapest_path = sys.maxint
for path in paths:
if path["cost"] <= cheapest_path:
cheapest_path = path["cost"]
for path in paths:
if goal_node in path["path"] and cheapest_path == path["cost"]:
return path
raise "BAM! Nothing matches!! WTF??"
 
def find_shortest_path(graph, start_node, goal_node):
paths = [{'path': [start_node], 'cost': 0}]
while not something_reaches_goal(paths, goal_node):
path = get_lowest_cost_path(paths)
new_paths = get_nodes_and_costs(graph, path)
paths.extend(new_paths)
paths.remove(path)
return get_path_that_reaches_goal(paths, goal_node)

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.