(self, src)
| 107 | for v, w in self.adjList[u])) |
| 108 | |
| 109 | def dijkstra(self, src): |
| 110 | # Flush old junk values in par[] |
| 111 | self.par = [-1] * self.num_nodes |
| 112 | # src is the source node |
| 113 | self.dist[src] = 0 |
| 114 | Q = PriorityQueue() |
| 115 | Q.insert((0, src)) # (dist from src, node) |
| 116 | for u in self.adjList.keys(): |
| 117 | if u != src: |
| 118 | self.dist[u] = sys.maxsize # Infinity |
| 119 | self.par[u] = -1 |
| 120 | |
| 121 | while not Q.isEmpty(): |
| 122 | u = Q.extract_min() # Returns node with the min dist from source |
| 123 | # Update the distance of all the neighbours of u and |
| 124 | # if their prev dist was INFINITY then push them in Q |
| 125 | for v, w in self.adjList[u]: |
| 126 | new_dist = self.dist[u] + w |
| 127 | if self.dist[v] > new_dist: |
| 128 | if self.dist[v] == sys.maxsize: |
| 129 | Q.insert((new_dist, v)) |
| 130 | else: |
| 131 | Q.decrease_key((self.dist[v], v), new_dist) |
| 132 | self.dist[v] = new_dist |
| 133 | self.par[v] = u |
| 134 | |
| 135 | # Show the shortest distances from src |
| 136 | self.show_distances(src) |
| 137 | |
| 138 | def show_distances(self, src): |
| 139 | print("Distance from node: {}".format(src)) |
no test coverage detected