Last active
April 18, 2020 23:25
-
-
Save ntreu14/3a890cfd3cba941f862a7c8473fa08b3 to your computer and use it in GitHub Desktop.
Implementation of Dijkstra's algorithm in Python with Advent of Code 2015 Day 9 input
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import math | |
lines = [ | |
"Faerun to Norrath = 129", | |
"Faerun to Tristram = 58", | |
"Faerun to AlphaCentauri = 13", | |
"Faerun to Arbre = 24", | |
"Faerun to Snowdin = 60", | |
"Faerun to Tambi = 71", | |
"Faerun to Straylight = 67", | |
"Norrath to Tristram = 142", | |
"Norrath to AlphaCentauri = 15", | |
"Norrath to Arbre = 135", | |
"Norrath to Snowdin = 75", | |
"Norrath to Tambi = 82", | |
"Norrath to Straylight = 54", | |
"Tristram to AlphaCentauri = 118", | |
"Tristram to Arbre = 122", | |
"Tristram to Snowdin = 103", | |
"Tristram to Tambi = 49", | |
"Tristram to Straylight = 97", | |
"AlphaCentauri to Arbre = 116", | |
"AlphaCentauri to Snowdin = 12", | |
"AlphaCentauri to Tambi = 18", | |
"AlphaCentauri to Straylight = 91", | |
"Arbre to Snowdin = 129", | |
"Arbre to Tambi = 53", | |
"Arbre to Straylight = 40", | |
"Snowdin to Tambi = 15", | |
"Snowdin to Straylight = 99", | |
"Tambi to Straylight = 70" | |
] | |
def buildGraph(input): | |
graph = {} | |
# Build a dictionary of nodes to its edges with their weights | |
for line in input: | |
print (line) | |
bySpaces = line.split(' ') | |
source = bySpaces[0] | |
destination = bySpaces[2] | |
weight = bySpaces[4] | |
# This problem calls for an an UNDIRECTED graph | |
if source not in graph: | |
# source -> destintion edge | |
graph[source] = set([(destination, int(weight))]) | |
if destination not in graph: | |
# destination -> source edge | |
graph[destination] = set([(source, int(weight))]) | |
if source in graph: | |
# Add the source -> destination edge to the set of edges | |
s = graph[source] | |
s.add((destination, int(weight))) | |
graph[source] = s | |
# Add the destination -> source edge to the set of edges | |
d = graph[destination] | |
d.add((source, int(weight))) | |
graph[destination] = d | |
return graph | |
def getNeighbors(g, v, q): | |
edgesAndWeights = g[v] | |
justEdges = set(map(lambda t: t[0], edgesAndWeights)) | |
return q.intersection(justEdges) | |
def findWeightFromVToU(g, v, u): | |
edgesToWeights = dict(g[v]) | |
return edgesToWeights[u] | |
def distWithOnlyInQ(q, dist): | |
a = {} | |
for key, v in dist.items(): | |
if key in q: | |
a[key] = v | |
return a | |
def dijkstra(g, s): | |
q = set() | |
dist = {} | |
for v in g.keys(): | |
if v is not s: | |
dist[v] = math.inf | |
q.add(v) | |
dist[s] = 0 | |
while not len(q) == 0: | |
m = distWithOnlyInQ(q, dist) | |
v = min(m, key=m.get) | |
q.remove(v) | |
for neighbor in getNeighbors(g, v, q): | |
alt = dist[v] + findWeightFromVToU(g, v, neighbor) | |
if alt < dist[neighbor]: | |
dist[neighbor] = alt | |
return dist | |
graph = buildGraph(lines) | |
paths = dijkstra(graph, "Faerun") | |
print(paths) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment