SHARE
TWEET

Untitled

a guest Jan 23rd, 2019 63 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Graph:
  2.     def __init__(self):
  3.         self.graph = {
  4.            'A': {'B': 10, 'D': 4, 'F': 10},
  5.            'B': {'E': 5, 'J': 10, 'I': 17},
  6.            'C': {'A': 4, 'D': 10, 'E': 16},
  7.            'D': {'F': 12, 'G': 21},
  8.            'E': {'G': 4},
  9.            'F': {'H': 3},
  10.            'G': {'J': 3},
  11.            'H': {'G': 3, 'J':5},
  12.            'I': {},
  13.            'J': {'I': 8}
  14.         }
  15.  
  16.     def shortpath(self, start, end):
  17.         D = {}
  18.         P = {}
  19.  
  20.          for knote in self.graph.keys():
  21.             D[knote] = - 1  
  22.             P[knote] = ""  
  23.  
  24.         D[start] = 0  
  25.  
  26.  
  27.         unvisited_n = list(self.graph.keys())
  28.  
  29.         while len(unvisited_n) > 0:
  30.  
  31.             shortest = None
  32.             knote = ''
  33.             for temp_node in unvisited_n:
  34.                 if shortest == None:
  35.                     shortest = D[temp_node]
  36.                     node = temp_node
  37.                 elif D[temp_node] < shortest:
  38.                     shortest = D[temp_node]
  39.                     knote = temp_node
  40.  
  41.                 if knote in unvisited_n:
  42.                     unvisited_n.remove(knote)
  43.  
  44.  
  45.         for c_knote, v_value in self.graph[knote].items():
  46.             if D[c_knote] < D[knote] + v_value:
  47.                 D[c_knote] = D[knote] + v_value
  48.  
  49.                 P[c_knote] = knote
  50.  
  51.                 path = []
  52.  
  53.                 knote = end
  54.  
  55.  
  56.         while not (knote == start):
  57.             if path.count(knote) == 0:
  58.                 path.insert(0, knote)
  59.                 knote = P[knote]  
  60.             else:
  61.                 break
  62.                 path.insert(0, start)
  63.             return path
  64.  
  65. def main():
  66.     gg = Graph()
  67.     path = gg.shortpath('C', 'I')
  68.     print(path)
  69.  
  70. if __name__ == '__main__':
  71.     main()
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top