Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #! /usr/bin/python3
- import priority_queue
- from collections import namedtuple
- import time
- import sys
- Edge = namedtuple('Edge', ['vertex', 'weight'])
- class Graph(object):
- def __init__(self, vertex_count):
- self.vertex_count = vertex_count
- self.adjacency_list = [[] for _ in range(vertex_count)]
- def add_edge(self, source, destination, weight):
- assert source < self.vertex_count
- assert destination < self.vertex_count
- self.adjacency_list[source].append(Edge(destination, weight))
- ''' To get undirected graph uncomment this'''
- # self.adjacency_list[destination].append(Edge(source, weight))
- ''' ~~~~~~~~~~~~~~~~ :--) ~~~~~~~~~~~~~~~~~'''
- def get_edge(self, vertex):
- for e in self.adjacency_list[vertex]:
- yield e
- def get_vertex(self):
- for v in range(self.vertex_count):
- yield v
- def dijkstra(graph, source, destination):
- q = priority_queue.PriorityQueue([])
- parents = []
- distances = []
- start_weight = float("inf")
- for i in graph.get_vertex():
- weight = start_weight
- if source == i:
- weight = 0
- distances.append(weight)
- parents.append(None)
- q.insert(source, 0)
- while not q.empty():
- v_tuple = q.pop(1)
- v = v_tuple.label
- if v_tuple.priority == float("inf"):
- return float("inf"), float("inf")
- for e in graph.get_edge(v):
- candidate_distance = distances[v] + e.weight
- if distances[e.vertex] > candidate_distance:
- distances[e.vertex] = candidate_distance
- parents[e.vertex] = v
- q.insert(e.vertex, distances[e.vertex])
- shortest_path = []
- ending = destination
- while ending is not None:
- shortest_path.append(ending)
- ending = parents[ending]
- shortest_path.reverse()
- return shortest_path, distances[destination]
- # g = Graph(n) gdzie n --> ilość wierzchołków
- # g.add_edge(start, end, cost)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement