• Sign Up
• Login
• API
• FAQ
• Tools
• Archive
daily pastebin goal
7%
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.

Top