Skip to content

Instantly share code, notes, and snippets.

@yukpiz yukpiz/dijkstra.py
Last active Aug 29, 2015

Embed
What would you like to do?
Dijkstra algorithm.
nodes = {
"A": ["", ""],
"B": ["", ""],
"C": ["", ""],
"D": ["", ""],
}
connects = [
["A", "B", "10"],
["B", "C", "10"],
["C", "D", "10"],
["A", "D", "31"],
]
start = "A"
goal = "D"
def initStart(start):
nodes[start] = [start, 0]
def nodeTo(base):
loopCount = 0
for connect in connects:
loopCount += 1
if connect[0] == base:
target = connect[1]
currentCost = int(nodes[base][1])
rootCost = int(connect[2])
if nodes[target][0] == "" or int(nodes[target][1]) > currentCost + rootCost:
nodes[target][0] = base
nodes[target][1] = str(currentCost + rootCost)
loopCount += nodeTo(target)
return loopCount
initStart(start)
print nodeTo(start)
print nodes
print "=" * 30
print nodes[goal][1]
print "=" * 30
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.