Implementation of Dijkstra's algorithm in Python with Advent of Code 2015 Day 9 input

dijkstra.py

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)