def shortestPath(graph,start,end):
	"""
	Find a single shortest path from the given start vertex
	to the given end vertex.
	The input has the same conventions as Dijkstra().
	The output is a list of the vertices in order along
	the shortest path.
	"""

	final_distances,predecessors = Dijkstra(graph,start,end)
	path = []
	while 1:
		path.append(end)
		if end == start: break
		end = predecessors[end]
	path.reverse()
	return path

	Find a single shortest path from the given start vertex
	to the given end vertex.
	The input has the same conventions as Dijkstra().
	The output is a list of the vertices in order along
	the shortest path.
	
recipes/Python/577343_Dijkstralgorithm_shortest/recipe-577343.py