Solution for https://itchallengeforfuture.postfinance.ch/en/

adjacency_matrix_graphy.py

import math

class Node:

  def __init__(self, name, x, y, indexloc=None):
    self.name = name
    self.x = x
    self.y = y
    self.index = indexloc


class Graph:

  @classmethod
  def create_from_nodes(self, nodes):
    return Graph(len(nodes), len(nodes), nodes)

  def __init__(self, row, col, nodes=None):
    # set up an adjacency matrix
    self.adj_mat = [[0] * col for _ in range(row)]
    self.nodes = nodes
    for i in range(len(self.nodes)):
      self.nodes[i].index = i

  # Conncects from node1 to node2
  # Note row is source, column is destination
  # Updated to allow weighted edges (supporting dijkstra's alg)
  def connect_dir(self, node1, node2, weight=1):
    node1, node2 = self.get_index_from_node(
      node1), self.get_index_from_node(node2)
    self.adj_mat[node1][node2] = weight

  # Optional weight argument to support dijkstra's alg
  def connect(self, node1, node2):
    weight = math.hypot( node2.x - node1.x, node2.y - node1.y)
    self.connect_dir(node1, node2, weight)
    self.connect_dir(node2, node1, weight)

  # Get node row, map non-zero items to their node in the self.nodes array
  # Select any non-zero elements, leaving you with an array of nodes
  # which are connections_to (for a directed graph)
  # Return value: array of tuples (node, weight)
  def connections_from(self, node):
    node = self.get_index_from_node(node)
    return [(self.nodes[col_num], self.adj_mat[node][col_num]) for col_num in range(len(self.adj_mat[node])) if self.adj_mat[node][col_num] != 0]

  # Map matrix to column of node
  # Map any non-zero elements to the node at that row index
  # Select only non-zero elements
  # Note for a non-directed graph, you can use connections_to OR
  # connections_from
  # Return value: array of tuples (node, weight)
  def connections_to(self, node):
    node = self.get_index_from_node(node)
    column = [row[node] for row in self.adj_mat]
    return [(self.nodes[row_num], column[row_num]) for row_num in range(len(column)) if column[row_num] != 0]

  def print_adj_mat(self):
    for row in self.adj_mat:
      print(row)

  def node(self, index):
    return self.nodes[index]

  def remove_conn(self, node1, node2):
    self.remove_conn_dir(node1, node2)
    self.remove_conn_dir(node2, node1)

  # Remove connection in a directed manner (nod1 to node2)
  # Can accept index number OR node object
  def remove_conn_dir(self, node1, node2):
    node1, node2 = self.get_index_from_node(
      node1), self.get_index_from_node(node2)
    self.adj_mat[node1][node2] = 0

  # Can go from node 1 to node 2?
  def can_traverse_dir(self, node1, node2):
    node1, node2 = self.get_index_from_node(
      node1), self.get_index_from_node(node2)
    return self.adj_mat[node1][node2] != 0

  def has_conn(self, node1, node2):
    return self.can_traverse_dir(node1, node2) or self.can_traverse_dir(node2, node1)

  def add_node(self, node):
      self.nodes.append(node)
      node.index = len(self.nodes) - 1
      for row in self.adj_mat:
        row.append(0)
      self.adj_mat.append([0] * (len(self.adj_mat) + 1))

  # Get the weight associated with travelling from n1
  # to n2. Can accept index numbers OR node objects
  def get_weight(self, n1, n2):
    node1, node2 = self.get_index_from_node(
      n1), self.get_index_from_node(n2)
    return self.adj_mat[node1][node2]

  # Allows either node OR node indices to be passed into
  def get_index_from_node(self, node):
    if not isinstance(node, Node) and not isinstance(node, int):
      raise ValueError("node must be an integer or a Node object")
    if isinstance(node, int):
      return node
    else:
      return node.index

  def dijkstra(self, node):
    # Get index of node (or maintain int passed in)
    nodenum = self.get_index_from_node(node)
    # Make an array keeping track of distance from node to any node
    # in self.nodes. Initialize to infinity for all nodes but the 
    # starting node, keep track of "path" which relates to distance.
    # Index 0 = distance, index 1 = node hops
    dist = [None] * len(self.nodes)
    for i in range(len(dist)):
      dist[i] = [float("inf")]
      dist[i].append([self.nodes[nodenum]])
    
    dist[nodenum][0] = 0
    # Queue of all nodes in the graph
    # Note the integers in the queue correspond to indices of node
    # locations in the self.nodes array
    queue = [i for i in range(len(self.nodes))]
    # Set of numbers seen so far
    seen = set()
    while len(queue) > 0:
      # Get node in queue that has not yet been seen
      # that has smallest distance to starting node
      min_dist = float("inf")
      min_node = None
      for n in queue: 
        if dist[n][0] < min_dist and n not in seen:
          min_dist = dist[n][0]
          min_node = n
      
      # Add min distance node to seen, remove from queue
      queue.remove(min_node)
      seen.add(min_node)
      # Get all next hops 
      connections = self.connections_from(min_node)
      # For each connection, update its path and total distance from 
      # starting node if the total distance is less than the current distance
      # in dist array
      for (node, weight) in connections: 
        tot_dist = weight + min_dist
        if tot_dist < dist[node.index][0]:
          dist[node.index][0] = tot_dist
          dist[node.index][1] = list(dist[min_node][1])
          dist[node.index][1].append(node)
    return dist

s  = Node("PostFinance HQ",3,5)

a1 = Node("a1",10,8)
a2 = Node("a2",11,3)
a3 = Node("a3",14,7)
a4 = Node("a4",15,1)
a5 = Node("a5",18,5)
a  = Node("Powercoders",22,2)

b1 = Node("b1",26,4)
b2 = Node("b2",35,8)
b3 = Node("b3",26,9)
b4 = Node("b4",28,13)
b5 = Node("b5",19,9)
b  = Node("Educreators",19,13)

c1 = Node("c1",21,15)
c2 = Node("c2",24,17)
c3 = Node("c3",30,15)
c4 = Node("c4",34,17)
c5 = Node("c5",46,15)
c  = Node("DSD Foundation",38,14)

e1 = Node("e1",42,13)
e2 = Node("e2",41,2)
e3 = Node("e3",46,9)
e4 = Node("e4",48,3)
e5 = Node("e5",51,14)
e  = Node("Charity Event",54,8)

g = Graph.create_from_nodes([s,a1,a2,a3,a4,a5,a,b1,b2,b3,b4,b5,b,c1,c2,c3,c4,c5,c,e1,e2,e3,e4,e5,e])

g.connect(s,a1)
g.connect(s,a2)
g.connect(a1,a3)
g.connect(a2,a4)
g.connect(a2,a5)
g.connect(a3,a5)
g.connect(a4,a)
g.connect(a5,a)

g.connect(a,b1)
g.connect(a,b3)
g.connect(b1,b2)
g.connect(b2,b3)
g.connect(b2,b4)
g.connect(b3,b4)
g.connect(b3,b5)
g.connect(b4,b)
g.connect(b5,b)

g.connect(b,c1)
g.connect(c1,c2)
g.connect(c2,c3)
g.connect(c2,c4)
g.connect(c3,c)
g.connect(c4,c5)
g.connect(c5,c)

g.connect(c,e1)
g.connect(e1,e2)
g.connect(e1,e5)
g.connect(e2,e3)
g.connect(e2,e4)
g.connect(e3,e)
g.connect(e4,e)
g.connect(e5,e)

#g.print_adj_mat()
print([(weight, [n.name for n in node]) for (weight, node) in g.dijkstra(s)])