dijkstras-algorithm.py

input_data = ['1', '4 5', 'S V 1', 'S W 4', 'V W 2', 'V T 6', 'W T 3', 'S']
my_graph = {
	'A': {'B': 7, 'C': 8},
	'B': {'A': 7, 'F': 2},
	'C': {'A': 8, 'F': 6, 'G': 4},
	'D': {'F': 8},
	'E': {'H': 1},
	'F': {'B': 2, 'C': 6, 'D': 8, 'G': 9, 'H': 3},
	'G': {'C': 4, 'F': 9},
	'H': {'E': 1, 'F': 3}
}

# for reference {'S': {'W': '4', 'V': '1'}, 'T': {}, 'W': {'T': '3'}, 'V': {'T': '6', 'W': '2'}}

def build_graph(array, edge_count):
	graph = {}
	# follow all edges to create graph
	for i in xrange(0, edge_count):
		x, y, weight = array[i].split()
		# add all tail nodes to graph
		if x in graph:
			graph[x][y] = int(weight)
		else:
			graph[x] = {y: int(weight)}

		# add all head nodes to graph
		if y not in graph:
			graph[y]  = {}

	return graph, i


def next_possible_node(graph, node, visited, distances, graph_keys):
	possible_next_nodes = []
	for node_name, weight in graph[node].items():
		if node_name in graph_keys:
			possible_next_nodes.append({
				'node_name': node_name,
				'distance': distances[node]+weight
			})

	return min(possible_next_nodes, key=lambda n: n['distance']) if len(possible_next_nodes) > 0 else None


def single_source_shortest_path(graph, start):
	visited = set([start])
	graph_keys = set(graph.keys())-visited
	distances = {start:0}
	distance_list = [0]

	while graph_keys:
		scored_nodes = []
		for node in visited:
			new_node = next_possible_node(graph, node, visited, distances, graph_keys)
			if new_node:
				scored_nodes.append(new_node)

		if len(scored_nodes) > 0:
			next_node = min(scored_nodes, key=lambda n: n['distance'])
		else:
			continue

		visited.add(next_node['node_name'])
		distances[next_node['node_name']] = next_node['distance']
		distance_list.append(next_node['distance'])
		graph_keys = graph_keys-visited
	
	return distances, distance_list


def answer_question(std_in, graph=None, start_node_value=None):
	test_cases = int(std_in[0])
	del std_in[0]
	num_nodes, num_edges = map(int, std_in[0].split())
	del std_in[0]
	
	# build the graph based on edges, get our start node
	g, s = build_graph(std_in, num_edges) if not graph else graph
	start_node_value = std_in[s+1] if not start_node_value else start_node_value

	return single_source_shortest_path(g, start_node_value)

print answer_question(input_data)