Home > front end >  Can't index through graph containing string values
Can't index through graph containing string values

Time:11-21

My goal im to be able to read the shortest distance between a specific building between all other buildings using the Dijkstra algorithm. I believe if I can fix the error, I will be able to complete my goal. The error below stops at a for loop, where it's trying to index through the vertices. I think it might have to do with the graph not containing an integer datatype, but that shouldn't matter because it should only be comparing the numbers in the graph. If someone could point me in the right direction so I can understand what I am doing wrong, that would be great.

Traceback (most recent call last): File "main.py", line 26, in dijkstra for v in self.graph[u]: KeyError: 0

import sys 
  
class Graph(): 
  
  def __init__(self, vertices): 
    self.V = vertices 
    self.graph = {}
    
  def min_distance(self,distance,traversed):
    min_index = 0 
    min_value = sys.maxsize
    for i in range(self.V):
      if traversed[i] is False and min_value > distance[i]:
        min_value = distance[i]
        min_index = i
    return min_index
    
  def dijkstra(self,source):
    distance = [sys.maxsize] * self.V
    traversed = [False] * self.V
    distance[source] = 0
        
    for i  in range(self.V):
      u = self.min_distance(distance,traversed)
      traversed[u] = True
      for v in self.graph[u]:               #ERROR
        if(traversed[v] is False):
          distance[v] = min(distance[v],distance[u] self.graph[u][v])
    print("from the give source vertex -- > ",source)
    for vertex in range(self.V):
      print("Vertex ",vertex," --> Distance = ",distance[vertex])
                
g  = Graph(19)

g.graph = {
    'College Square':{'Lewis Science Center':200, 'Prince Center':300},
    'Lewis Science Center':{'College Square':200, 'Speech Language Hearing':250, 'Computer Science':150},
    'Speech Language Hearing':{'Lewis Science Center':250, 'Burdick':100, 'Maintenance College':120},
    'Computer Science':{'Prince Center':80, 'Torreyson Library':40, 'Burdick':30, 'Lewis Science Center':150},
    'Burdick':{'Computer Science':30, 'Speech Language Hearing':100, 'Torreyson Library':80, 'Maintenance College':300, 'McALister Hall':200},
    'Prince Center':{'College Square':300, 'Computer Science':80, 'Torreyson Library':30, 'Police Dept.':100},
    'Torreyson Library':{'Prince Center':30, 'Computer Science':40, 'Burdick':80, 'Old Main':30},
    'Old Main':{'Torreyson Library':30, 'Police Dept.':200, 'Fine Art':90, 'McALister Hall':100},
    'Maintenance College':{'Speech Language Hearing':120, 'Burdick':300, 'McALister Hall':150, 'Wingo':100, 'New Business Building':150, 'Oak Tree Apt.':160},
    'Police Dept.':{'Prince Center':100, 'Old Main':200, 'Fine Art':50, 'Student Health Center':100},
    'Fine Art':{'Police Dept.':50, 'Old Main':90, 'McALister Hall':180, 'Student Center':80},
    'McALister Hall':{'Fine Art':180, 'Old Main':100, 'Burdick':200, 'Maintenance College':150, 'Wingo':50, 'Student Center':100},
    'Student Center':{'Fine Art':80, 'McALister Hall':100, 'Wingo':100, 'New Business Building':110, 'Student Health Center':50},
    'Wingo':{'Student Center':100, 'McALister Hall':50, 'Maintenance College':100, 'New Business Building':50},
    'Student Health Center':{'Police Dept.':100, 'Student Center':50, 'Brewer-Hegeman':200},
    'New Business Building':{'Student Center':110, 'Wingo':50, 'Maintenance College':150, 'Oak Tree Apt.':30, 'Brewer-Hegeman':20},
    'Oak Tree Apt.':{'Maintenance College':160, 'New Business Building':30, 'Brewer-Hegeman':40},
    'Brewer-Hegeman':{'Student Health Center':200, 'New Business Building':20, 'Oak Tree Apt.':40, 'Bear village Apt.':350},
    'Bear village Apt.':{'Brewer-Hegeman':350}

     }

g.dijkstra(0)

CodePudding user response:

changed to work with strings"

import sys 
  
class Graph(): 
  
  def __init__(self, vertices): 
    self.V = vertices 
    self.graph = {}
    
  def min_distance(self,distance,traversed):
    min_index = 0 
    min_value = sys.maxsize
    for i in self.graph:
      if traversed[i] is False and min_value > distance[i]:
        min_value = distance[i]
        min_index = i
    return min_index
    
  def dijkstra(self,source):
    distance={}
    traversed={}
    for i in self.graph:
        traversed[i] = False
        distance[i] = sys.maxsize
    distance[source] = 0
        
    for i  in self.graph:
      u = self.min_distance(distance,traversed)
      traversed[u] = True
      for v in self.graph[u]:               #ERROR
        if(traversed[v] is False):
          distance[v] = min(distance[v],distance[u] self.graph[u][v])
    print("from the give source vertex -- > ",source)
    for vertex in self.graph:
      print("Vertex ",vertex," --> Distance = ",distance[vertex])
                
g  = Graph(19)

g.graph = {
    'College Square':{'Lewis Science Center':200, 'Prince Center':300},
    'Lewis Science Center':{'College Square':200, 'Speech Language Hearing':250, 'Computer Science':150},
    'Speech Language Hearing':{'Lewis Science Center':250, 'Burdick':100, 'Maintenance College':120},
    'Computer Science':{'Prince Center':80, 'Torreyson Library':40, 'Burdick':30, 'Lewis Science Center':150},
    'Burdick':{'Computer Science':30, 'Speech Language Hearing':100, 'Torreyson Library':80, 'Maintenance College':300, 'McALister Hall':200},
    'Prince Center':{'College Square':300, 'Computer Science':80, 'Torreyson Library':30, 'Police Dept.':100},
    'Torreyson Library':{'Prince Center':30, 'Computer Science':40, 'Burdick':80, 'Old Main':30},
    'Old Main':{'Torreyson Library':30, 'Police Dept.':200, 'Fine Art':90, 'McALister Hall':100},
    'Maintenance College':{'Speech Language Hearing':120, 'Burdick':300, 'McALister Hall':150, 'Wingo':100, 'New Business Building':150, 'Oak Tree Apt.':160},
    'Police Dept.':{'Prince Center':100, 'Old Main':200, 'Fine Art':50, 'Student Health Center':100},
    'Fine Art':{'Police Dept.':50, 'Old Main':90, 'McALister Hall':180, 'Student Center':80},
    'McALister Hall':{'Fine Art':180, 'Old Main':100, 'Burdick':200, 'Maintenance College':150, 'Wingo':50, 'Student Center':100},
    'Student Center':{'Fine Art':80, 'McALister Hall':100, 'Wingo':100, 'New Business Building':110, 'Student Health Center':50},
    'Wingo':{'Student Center':100, 'McALister Hall':50, 'Maintenance College':100, 'New Business Building':50},
    'Student Health Center':{'Police Dept.':100, 'Student Center':50, 'Brewer-Hegeman':200},
    'New Business Building':{'Student Center':110, 'Wingo':50, 'Maintenance College':150, 'Oak Tree Apt.':30, 'Brewer-Hegeman':20},
    'Oak Tree Apt.':{'Maintenance College':160, 'New Business Building':30, 'Brewer-Hegeman':40},
    'Brewer-Hegeman':{'Student Health Center':200, 'New Business Building':20, 'Oak Tree Apt.':40, 'Bear village Apt.':350},
    'Bear village Apt.':{'Brewer-Hegeman':350}

     }

g.dijkstra('College Square')
  • Related