daily pastebin goal
27%
SHARE
TWEET

Untitled

a guest Jun 13th, 2018 62 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #! /usr/bin/python3
  2. import priority_queue
  3. from collections import namedtuple
  4. import time
  5. import sys
  6.  
  7. Edge = namedtuple('Edge', ['vertex', 'weight'])
  8.  
  9.  
  10. class Graph(object):
  11.     def __init__(self, vertex_count):
  12.         self.vertex_count = vertex_count
  13.         self.adjacency_list = [[] for _ in range(vertex_count)]
  14.  
  15.     def add_edge(self, source, destination, weight):
  16.         assert source < self.vertex_count
  17.         assert destination < self.vertex_count
  18.         self.adjacency_list[source].append(Edge(destination, weight))
  19.  
  20.         ''' To get undirected graph uncomment this'''
  21.         # self.adjacency_list[destination].append(Edge(source, weight))
  22.         ''' ~~~~~~~~~~~~~~~~ :--) ~~~~~~~~~~~~~~~~~'''
  23.  
  24.     def get_edge(self, vertex):
  25.         for e in self.adjacency_list[vertex]:
  26.             yield e
  27.  
  28.     def get_vertex(self):
  29.         for v in range(self.vertex_count):
  30.             yield v
  31.  
  32.  
  33. def dijkstra(graph, source, destination):
  34.     q = priority_queue.PriorityQueue([])
  35.     parents = []
  36.     distances = []
  37.     start_weight = float("inf")
  38.  
  39.     for i in graph.get_vertex():
  40.         weight = start_weight
  41.         if source == i:
  42.             weight = 0
  43.         distances.append(weight)
  44.         parents.append(None)
  45.  
  46.     q.insert(source, 0)
  47.  
  48.     while not q.empty():
  49.         v_tuple = q.pop(1)
  50.         v = v_tuple.label
  51.  
  52.         if v_tuple.priority == float("inf"):
  53.             return float("inf"), float("inf")
  54.  
  55.         for e in graph.get_edge(v):
  56.  
  57.             candidate_distance = distances[v] + e.weight
  58.             if distances[e.vertex] > candidate_distance:
  59.                 distances[e.vertex] = candidate_distance
  60.                 parents[e.vertex] = v
  61.                 q.insert(e.vertex, distances[e.vertex])
  62.  
  63.     shortest_path = []
  64.     ending = destination
  65.     while ending is not None:
  66.         shortest_path.append(ending)
  67.         ending = parents[ending]
  68.  
  69.     shortest_path.reverse()
  70.  
  71.     return shortest_path, distances[destination]
  72.  
  73. # g = Graph(n) gdzie n --> ilość wierzchołków
  74. # g.add_edge(start, end, cost)
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