Implementation of Dijksra's Algorithm and a modified Dijkstra's Algorithm with Seidel's Heuristics to bound Dijkstra's computation to a localized neighborhood

dijkstra.py

import sys

class Graph:
  def __init__(self, n):
    self.n = n
    self.graph = [[0 for j in range(n)] for i in range(n)]

  def insertEdge(self, u, v, w):
    self.graph[u - 1][v - 1] = w
    if(w > 50):
      self.graph[v - 1][u - 1] = 1
    else:
      self.graph[v - 1][u - 1] = abs(50 - w)

  def printDist(self, dist):
    print("vertex", "\t", "Distance")
    for i in range(self.n):
      print(i, "\t", dist[i])

  def getMinNode(self, dist, computed):
    minval = sys.maxsize
    node = -1
    compute = 0

    for i in range(self.n):
      if(not computed[i] and dist[i] < minval):
        compute += 1
        minval = dist[i]
        node = i

    return [node, compute]


  def dijkstra(self, src):
    compute = 0
    dist = [sys.maxsize for i in range(self.n)]
    dist[src] = 0
    computed = [False for i in range(self.n)]
    frm = [-1 for i in range(self.n)]

    for _ in range(self.n):
      [u, cmp] = self.getMinNode(dist, computed)
      compute += cmp
      computed[u] = True
      compute += 1
  
      for k in range(self.n):
        if(not computed[k] and self.graph[u][k] > 0 and (dist[u] + self.graph[u][k]) < dist[k]):
          compute += 1
          dist[k] = dist[u] + self.graph[u][k]
          frm[k] = u

      if(dist[3] < 500):
        print("Distance: ", dist[3])
        print("Compute: ", compute)
        return

    self.printDist(dist)

g = Graph(30)
g.insertEdge(1, 2, 100)
g.insertEdge(1, 3, 200)
g.insertEdge(2, 4, 140)
g.insertEdge(3, 4, 70)
g.insertEdge(1, 5, 1)
g.insertEdge(5, 6, 2)
g.insertEdge(5, 7, 2)
g.insertEdge(5, 8, 1)
g.insertEdge(8, 9, 2)
g.insertEdge(8, 10, 2)
g.insertEdge(8, 11, 1)
g.insertEdge(11, 12, 2)
g.insertEdge(11, 13, 2)
g.insertEdge(11, 14, 1)
g.insertEdge(14, 15, 2)
g.insertEdge(14, 16, 2)
g.insertEdge(14, 17, 1)
g.insertEdge(17, 18, 2)
g.insertEdge(17, 19, 2)
g.insertEdge(17, 20, 1)
g.insertEdge(20, 21, 2)
g.insertEdge(20, 22, 2)
g.insertEdge(20, 23, 1)
g.insertEdge(23, 24, 2)
g.insertEdge(23, 25, 2)
g.insertEdge(23, 26, 1)
g.insertEdge(26, 27, 2)
g.insertEdge(26, 28, 2)
g.insertEdge(26, 29, 1)
g.insertEdge(29, 30, 1)

for i in range(100000):
  g.dijkstra(0)

seidel_dijkstra.py

import sys
from pprint import pprint

def matmul(a, b):
  n = len(a)
  result = [[0 for j in range(n)] for i in range(n)]
  for i in range(n):
    for j in range(n):
      for k in range(n):
        result[i][j] += a[i][k] * b[k][j]

  return result

def computeAdjacency(graph):
  return [[1 if graph[i][j] != 0 else 0 for j in range(len(graph))] for i in range(len(graph))]

def seidel(a):
  n = len(a)
  z = matmul(a, a)
  b = [[0 for j in range(n)] for i in range(n)]
  cnt = 0
  for i in range(n):
    for j in range(n):
      if(i != j and (a[i][j] == 1 or z[i][j] > 0)):
        b[i][j] = 1
        cnt += 1

  if(cnt == n * n - n):
    return [[(2 * b[i][j] - a[i][j]) for j in range(n)] for i in range(n)]

  t = seidel(b)
  x = matmul(t, a)

  degree = [sum([a[j][i] for j in range(n)]) for i in range(n)]
  result = [[0 for j in range(n)] for i in range(n)]

  for i in range(n):
    for j in range(n):
      if(x[i][j] >= t[i][j] * degree[j]):
        result[i][j] = 2 * t[i][j]
      else:
        result[i][j] = (2 * t[i][j]) - 1

  return result

class Graph:
  def __init__(self, n):
    self.n = n
    self.graph = [[0 for j in range(n)] for i in range(n)]

  def insertEdge(self, u, v, w):
    self.graph[u - 1][v - 1] = w
    if(w > 50):
      self.graph[v - 1][u - 1] = 1
    else:
      self.graph[v - 1][u - 1] = abs(50 - w)

  def printDist(self, dist):
    print("vertex", "\t", "Distance")
    for i in range(self.n):
      print(i, "\t", dist[i])

  def getMinNode(self, dist, computed, sh, steps):
    minval = sys.maxsize
    node = -1
    compute = 0

    for i in range(self.n):
      if(not computed[i] and dist[i] + (15 * ((sh[i] if sh[i] >= steps else 0))) ** 6 < minval):
        compute += 1
        minval = dist[i] + (15 * ((sh[i] if sh[i] >= steps else 0))) ** 6
        node = i
    #     print("Node: ", i)
    #     print("Distance: ", dist[i], " ,sh: ", sh[i])
    #     print("Minval: ", minval)

    # print("Return Node: ", node)
    return [node, compute]


  def dijkstra(self, src, dest, steps):
    compute = 0
    steps = 0
    dist = [sys.maxsize for i in range(self.n)]
    frm = [-1 for i in range(self.n)]
    dist[src] = 0
    computed = [False for i in range(self.n)]
    sh = [0 for i in range(self.n)]

    for _ in range(self.n):
      [u, cmp] = self.getMinNode(dist, computed, sh, steps)
      compute += cmp
      computed[u] = True
      compute += 1
      steps += 1
  
      for k in range(self.n):
        if(not computed[k] and self.graph[u][k] > 0 and (dist[u] + self.graph[u][k]) < dist[k]):
          compute += 1
          dist[k] = dist[u] + self.graph[u][k]
          sh[k] = steps
          frm[k] = u 

      if(frm[dest] != -1):
        print("Compute: ", compute)
        print("Distance: ", dist[dest])
        break


g = Graph(30)
g.insertEdge(1, 2, 100)
g.insertEdge(1, 3, 200)
g.insertEdge(2, 4, 140)
g.insertEdge(3, 4, 70)
g.insertEdge(1, 5, 1)
g.insertEdge(5, 6, 2)
g.insertEdge(5, 7, 2)
g.insertEdge(5, 8, 1)
g.insertEdge(8, 9, 2)
g.insertEdge(8, 10, 2)
g.insertEdge(8, 11, 1)
g.insertEdge(11, 12, 2)
g.insertEdge(11, 13, 2)
g.insertEdge(11, 14, 1)
g.insertEdge(14, 15, 2)
g.insertEdge(14, 16, 2)
g.insertEdge(14, 17, 1)
g.insertEdge(17, 18, 2)
g.insertEdge(17, 19, 2)
g.insertEdge(17, 20, 1)
g.insertEdge(20, 21, 2)
g.insertEdge(20, 22, 2)
g.insertEdge(20, 23, 1)
g.insertEdge(23, 24, 2)
g.insertEdge(23, 25, 2)
g.insertEdge(23, 26, 1)
g.insertEdge(26, 27, 2)
g.insertEdge(26, 28, 2)
g.insertEdge(26, 29, 1)
g.insertEdge(29, 30, 1)

step = seidel(computeAdjacency(g.graph))[0][3]
for i in range(100000):
  g.dijkstra(0, 3, step)