Ik probeer Dijkstra’s algoritme in python te implementeren met behulp van arrays. Dit is mijn implementatie.
def extract(Q, w):
m=0
minimum=w[0]
for i in range(len(w)):
if w[i]<minimum:
minimum=w[i]
m=i
return m, Q[m]
def dijkstra(G, s, t='B'):
Q=[s]
p={s:None}
w=[0]
d={}
for i in G:
d[i]=float('inf')
Q.append(i)
w.append(d[i])
d[s]=0
S=[]
n=len(Q)
while Q:
u=extract(Q,w)[1]
S.append(u)
#w.remove(extract(Q, d, w)[0])
Q.remove(u)
for v in G[u]:
if d[v]>=d[u]+G[u][v]:
d[v]=d[u]+G[u][v]
p[v]=u
return d, p
B='B'
A='A'
D='D'
G='G'
E='E'
C='C'
F='F'
G={B:{A:5, D:1, G:2}, A:{B:5, D:3, E:12, F:5}, D:{B:1, G:1, E:1, A:3}, G:{B:2, D:1, C:2}, C:{G:2, E:1, F:16}, E:{A:12, D:1, C:1, F:2}, F:{A:5, E:2, C:16}}
print "Assuming the start vertex to be B:"
print "Shortest distances", dijkstra(G, B)[0]
print "Parents", dijkstra(G, B)[1]
Ik verwacht dat het antwoord is:
Assuming the start vertex to be B:
Shortest distances {'A': 4, 'C': 4, 'B': 0, 'E': 2, 'D': 1, 'G': 2, 'F': 4}
Parents {'A': 'D', 'C': 'G', 'B': None, 'E': 'D', 'D': 'B', 'G': 'D', 'F': 'E'}
Het antwoord dat ik krijg is echter dit:
Assuming the start vertex to be B:
Shortest distances {'A': 4, 'C': 4, 'B': 0, 'E': 2, 'D': 1, 'G': 2, 'F': 10}
Parents {'A': 'D', 'C': 'G', 'B': None, 'E': 'D', 'D': 'B', 'G': 'D', 'F': 'A'}.
Voor het knooppunt F geeft het programma het verkeerde antwoord. Kan iemand me alsjeblieft vertellen waarom?
Antwoord 1, autoriteit 100%
Zoals anderen al hebben opgemerkt, is het bijna onmogelijk om fouten in uw code op te sporen, omdat er geen begrijpelijke namen van variabelen worden gebruikt.
Volgens het wiki-artikel over Dijkstra’s algoritme kan men het als volgt implementeren (en op een miljoen andere manieren):
nodes = ('A', 'B', 'C', 'D', 'E', 'F', 'G')
distances = {
'B': {'A': 5, 'D': 1, 'G': 2},
'A': {'B': 5, 'D': 3, 'E': 12, 'F' :5},
'D': {'B': 1, 'G': 1, 'E': 1, 'A': 3},
'G': {'B': 2, 'D': 1, 'C': 2},
'C': {'G': 2, 'E': 1, 'F': 16},
'E': {'A': 12, 'D': 1, 'C': 1, 'F': 2},
'F': {'A': 5, 'E': 2, 'C': 16}}
unvisited = {node: None for node in nodes} #using None as +inf
visited = {}
current = 'B'
currentDistance = 0
unvisited[current] = currentDistance
while True:
for neighbour, distance in distances[current].items():
if neighbour not in unvisited: continue
newDistance = currentDistance + distance
if unvisited[neighbour] is None or unvisited[neighbour] > newDistance:
unvisited[neighbour] = newDistance
visited[current] = currentDistance
del unvisited[current]
if not unvisited: break
candidates = [node for node in unvisited.items() if node[1]]
current, currentDistance = sorted(candidates, key = lambda x: x[1])[0]
print(visited)
Deze code is uitgebreider dan nodig en ik hoop dat u, als u uw code met de mijne vergelijkt, enkele verschillen opmerkt.
Het resultaat is:
{'E': 2, 'D': 1, 'G': 2, 'F': 4, 'A': 4, 'C': 3, 'B': 0}
Antwoord 2, autoriteit 27%
Deze implementatie gebruikt alleen array en heap ds.
import heapq as hq
import math
def dijkstra(G, s):
n = len(G)
visited = [False]*n
weights = [math.inf]*n
path = [None]*n
queue = []
weights[s] = 0
hq.heappush(queue, (0, s))
while len(queue) > 0:
g, u = hq.heappop(queue)
visited[u] = True
for v, w in G[u]:
if not visited[v]:
f = g + w
if f < weights[v]:
weights[v] = f
path[v] = u
hq.heappush(queue, (f, v))
return path, weights
G = [[(1, 6), (3, 7)],
[(2, 5), (3, 8), (4, -4)],
[(1, -2), (4, 7)],
[(2, -3), (4, 9)],
[(0, 2)]]
print(dijkstra(G, 0))
Ik hoop dat dit iemand kan helpen, het is een beetje laat.
Antwoord 3, Autoriteit 24%
Ik schreef het in een meer uitgebreide vorm om het duidelijker te maken voor een beginnende lezer:
def get_parent(pos):
return (pos + 1) // 2 - 1
def get_children(pos):
right = (pos + 1) * 2
left = right - 1
return left, right
def swap(array, a, b):
array[a], array[b] = array[b], array[a]
class Heap:
def __init__(self):
self._array = []
def peek(self):
return self._array[0] if self._array else None
def _get_smallest_child(self, parent):
return min([
it
for it in get_children(parent)
if it < len(self._array)
], key=lambda it: self._array[it], default=-1)
def _sift_down(self):
parent = 0
smallest = self._get_smallest_child(parent)
while smallest != -1 and self._array[smallest] < self._array[parent]:
swap(self._array, smallest, parent)
parent, smallest = smallest, self._get_smallest_child(smallest)
def pop(self):
if not self._array:
return None
swap(self._array, 0, len(self._array) - 1)
node = self._array.pop()
self._sift_down()
return node
def _sift_up(self):
index = len(self._array) - 1
parent = get_parent(index)
while parent != -1 and self._array[index] < self._array[parent]:
swap(self._array, index, parent)
index, parent = parent, get_parent(parent)
def add(self, item):
self._array.append(item)
self._sift_up()
def __bool__(self):
return bool(self._array)
def backtrack(best_parents, start, end):
if end not in best_parents:
return None
cursor = end
path = [cursor]
while cursor in best_parents:
cursor = best_parents[cursor]
path.append(cursor)
if cursor == start:
return list(reversed(path))
return None
def dijkstra(weighted_graph, start, end):
"""
Calculate the shortest path for a directed weighted graph.
Node can be virtually any hashable datatype.
:param start: starting node
:param end: ending node
:param weighted_graph: {"node1": {"node2": weight, ...}, ...}
:return: ["START", ... nodes between ..., "END"] or None, if there is no
path
"""
distances = {i: float("inf") for i in weighted_graph}
best_parents = {i: None for i in weighted_graph}
to_visit = Heap()
to_visit.add((0, start))
distances[start] = 0
visited = set()
while to_visit:
src_distance, source = to_visit.pop()
if src_distance > distances[source]:
continue
if source == end:
break
visited.add(source)
for target, distance in weighted_graph[source].items():
if target in visited:
continue
new_dist = distances[source] + weighted_graph[source][target]
if distances[target] > new_dist:
distances[target] = new_dist
best_parents[target] = source
to_visit.add((new_dist, target))
return backtrack(best_parents, start, end)
Antwoord 4, autoriteit 22%
Dit is niet mijn antwoord – mijn prof deed het veel efficiënter dan mijn poging. Hier is zijn aanpak, uiteraard met behulp van helper-functies voor de repetitieve taken
def dijkstra(graph, source):
vertices, edges = graph
dist = dict()
previous = dict()
for vertex in vertices:
dist[vertex] = float("inf")
previous[vertex] = None
dist[source] = 0
Q = set(vertices)
while len(Q) > 0:
u = minimum_distance(dist, Q)
print('Currently considering', u, 'with a distance of', dist[u])
Q.remove(u)
if dist[u] == float('inf'):
break
n = get_neighbours(graph, u)
for vertex in n:
alt = dist[u] + dist_between(graph, u, vertex)
if alt < dist[vertex]:
dist[vertex] = alt
previous[vertex] = u
return previous
Gegeven een grafiek
({‘A’, ‘B’, ‘C’, ‘D’}, {(‘A’, ‘B’, 5), (‘B’, ‘A’, 5), (‘B ‘, ‘C’, 10), (‘B’, ‘D’, 6), (‘C’, ‘D’, 2), (‘D’, ‘C’, 2)})
het commando print(dijkstra(graph, 'A')levert op
Momenteel gezien A met een afstand van 0
Momenteel wordt B overwogen met een afstand van 5
Momenteel gezien D met een afstand van 11
Momenteel gezien C met een afstand van 13
id est:
{‘C’: ‘D’, ‘D’: ‘B’, ‘A’: Geen, ‘B’: ‘A’} => in willekeurige volgorde
Antwoord 5, autoriteit 14%
Implementatie op basis van CLRS 2nd Ed. Hoofdstuk 24.3
dis deltas, pis voorgangers
import heapq
def dijkstra(g, s, t):
q = []
d = {k: sys.maxint for k in g.keys()}
p = {}
d[s] = 0
heapq.heappush(q, (0, s))
while q:
last_w, curr_v = heapq.heappop(q)
for n, n_w in g[curr_v]:
cand_w = last_w + n_w # equivalent to d[curr_v] + n_w
# print d # uncomment to see how deltas are updated
if cand_w < d[n]:
d[n] = cand_w
p[n] = curr_v
heapq.heappush(q, (cand_w, n))
print "predecessors: ", p
print "delta: ", d
return d[t]
def test():
og = {}
og["s"] = [("t", 10), ("y", 5)]
og["t"] = [("y", 2), ("x", 1)]
og["y"] = [("t", 3), ("x", 9), ("z", 2)]
og["z"] = [("x", 6), ("s", 7)]
og["x"] = [("z", 4)]
assert dijkstra(og, "s", "x") == 9
if __name__ == "__main__":
test()
Implementatie gaat ervan uit dat alle knooppunten worden weergegeven als sleutels. Als bijvoorbeeld node (bijv. “x” in het bovenstaande voorbeeld) niet is gedefinieerd als een sleutel in de og, zou deltas ddie sleutel missen en controleren of cand_w < d[n]zou niet correct werken.
Antwoord 6, autoriteit 5%
Ik had een oplossing nodig die ook het pad zou teruggeven, dus stelde ik een eenvoudige klas samen met ideeën uit meerdere vragen/antwoorden over Dijkstra:
class Dijkstra:
def __init__(self, vertices, graph):
self.vertices = vertices # ("A", "B", "C" ...)
self.graph = graph # {"A": {"B": 1}, "B": {"A": 3, "C": 5} ...}
def find_route(self, start, end):
unvisited = {n: float("inf") for n in self.vertices}
unvisited[start] = 0 # set start vertex to 0
visited = {} # list of all visited nodes
parents = {} # predecessors
while unvisited:
min_vertex = min(unvisited, key=unvisited.get) # get smallest distance
for neighbour, _ in self.graph.get(min_vertex, {}).items():
if neighbour in visited:
continue
new_distance = unvisited[min_vertex] + self.graph[min_vertex].get(neighbour, float("inf"))
if new_distance < unvisited[neighbour]:
unvisited[neighbour] = new_distance
parents[neighbour] = min_vertex
visited[min_vertex] = unvisited[min_vertex]
unvisited.pop(min_vertex)
if min_vertex == end:
break
return parents, visited
@staticmethod
def generate_path(parents, start, end):
path = [end]
while True:
key = parents[path[0]]
path.insert(0, key)
if key == start:
break
return path
Voorbeeld van grafiek en gebruik (tekening wordt gegenereerd met deze handige tool):
input_vertices = ("A", "B", "C", "D", "E", "F", "G")
input_graph = {
"A": {"B": 5, "D": 3, "E": 12, "F": 5},
"B": {"A": 5, "D": 1, "G": 2},
"C": {"E": 1, "F": 16, "G": 2},
"D": {"A": 3, "B": 1, "E": 1, "G": 1},
"E": {"A": 12, "C": 1, "D": 1, "F": 2},
"F": {"A": 5, "C": 16, "E": 2},
"G": {"B": 2, "C": 2, "D": 1}
}
start_vertex = "B"
end_vertex= "C"
dijkstra = Dijkstra(input_vertices, input_graph)
p, v = dijkstra.find_route(start_vertex, end_vertex)
print("Distance from %s to %s is: %.2f" % (start_vertex, end_vertex, v[end_vertex]))
se = dijkstra.generate_path(p, start_vertex, end_vertex)
print("Path from %s to %s is: %s" % (start_vertex, end_vertex, " -> ".join(se)))
Uitgang
Distance from B to C is: 3.00
Path from B to C is: B -> D -> E -> C
Antwoord 7
Stel een breekpunt in bij extract. U zult zien dat u vermeldingen van Q maar nooit van W. Al het andere is een dict, maar Q / W zijn een gepaarde array die u niet op de hoogte blijft. Je moet die twee synchroniseren, of ze vervangen door een dict. SPECIALE OPMERKING: Uiteindelijk, nadat het algoritme werkt, wilt u mogelijk Q / W vervangen door een lijst met randen en re-code de functie “Extract” met een prioritaire wachtrij (heapq-module).
Bovendien ziet u dat W altijd gewichten van 0 heeft voor de bron, en ‘inf’ voor alle andere knooppunten. U hebt de kritieke stap volledig overgeslagen waar u de kandidaat-afstanden bijwerkt.
Dus je neemt eigenlijk altijd het eerste pad dat je tegenkomt, in plaats van het kortste pad te selecteren. Je berekent later de daadwerkelijke afstand van dat pad, dus de geretourneerde reeks afstanden heeft werkelijke waarden, maar ze werden willekeurig gekozen en je hebt geen reden om te verwachten dat ze het kortst zal zijn.
Nadat je (onjuist) het volgende knooppunt hebt gevonden, kijk je naar alle randen. Dit had de cruciale stap moeten zijn die ik hierboven in de tweede paragraaf noemde, waar je de kandidaten voor het volgende knooppunt bijwerkt. In plaats daarvan doe je iets heel anders: je lijkt alle voorgaande oplossingen door te lopen (die gegarandeerd correct zijn en met rust gelaten moeten worden, als je dijkstra correct implementeert), en je zoekt naar een oplossing in twee stappen van source->current ->elk. De juiste bedoeling om daar naar te kijken zou zijn geweest om de volgende kandidaat van vorige paden toe te voegen aan het volgende knooppunt, maar omdat ze nooit worden toegevoegd, kijk je niet naar (vorige kortste pad) + (één stap), je kijkt alleen bij letterlijk twee knoopoplossingen.
Dus in feite loop je door alle mogelijke paden met twee knooppunten van de bron om de kortste paden te vinden. Dit is een complete fout en heeft niets met dijkstra te maken. Maar het werkt bijna op je kleine grafiek, waar de meeste van de juiste kortste paden tweestapspaden zijn.
(ps: ik ben het met iedereen eens over je variabelenamen. Je zou veel beter hebben gedaan als je uitgebreide namen had gebruikt om te vertellen wat die variabelen vertegenwoordigen. Ik moest ze hernoemen voordat ik je code kon analyseren.)
Antwoord 8
import sys
import heapq
class Node:
def __init__(self, name):
self.name = name
self.visited = False
self.adjacenciesList = []
self.predecessor = None
self.mindistance = sys.maxsize
def __lt__(self, other):
return self.mindistance < other.mindistance
class Edge:
def __init__(self, weight, startvertex, endvertex):
self.weight = weight
self.startvertex = startvertex
self.endvertex = endvertex
def calculateshortestpath(vertexlist, startvertex):
q = []
startvertex.mindistance = 0
heapq.heappush(q, startvertex)
while q:
actualnode = heapq.heappop(q)
for edge in actualnode.adjacenciesList:
tempdist = edge.startvertex.mindistance + edge.weight
if tempdist < edge.endvertex.mindistance:
edge.endvertex.mindistance = tempdist
edge.endvertex.predecessor = edge.startvertex
heapq.heappush(q,edge.endvertex)
def getshortestpath(targetvertex):
print("The value of it's minimum distance is: ",targetvertex.mindistance)
node = targetvertex
while node:
print(node.name)
node = node.predecessor
node1 = Node("A");
node2 = Node("B");
node3 = Node("C");
node4 = Node("D");
node5 = Node("E");
node6 = Node("F");
node7 = Node("G");
node8 = Node("H");
edge1 = Edge(5,node1,node2);
edge2 = Edge(8,node1,node8);
edge3 = Edge(9,node1,node5);
edge4 = Edge(15,node2,node4);
edge5 = Edge(12,node2,node3);
edge6 = Edge(4,node2,node8);
edge7 = Edge(7,node8,node3);
edge8 = Edge(6,node8,node6);
edge9 = Edge(5,node5,node8);
edge10 = Edge(4,node5,node6);
edge11 = Edge(20,node5,node7);
edge12 = Edge(1,node6,node3);
edge13 = Edge(13,node6,node7);
edge14 = Edge(3,node3,node4);
edge15 = Edge(11,node3,node7);
edge16 = Edge(9,node4,node7);
node1.adjacenciesList.append(edge1);
node1.adjacenciesList.append(edge2);
node1.adjacenciesList.append(edge3);
node2.adjacenciesList.append(edge4);
node2.adjacenciesList.append(edge5);
node2.adjacenciesList.append(edge6);
node8.adjacenciesList.append(edge7);
node8.adjacenciesList.append(edge8);
node5.adjacenciesList.append(edge9);
node5.adjacenciesList.append(edge10);
node5.adjacenciesList.append(edge11);
node6.adjacenciesList.append(edge12);
node6.adjacenciesList.append(edge13);
node3.adjacenciesList.append(edge14);
node3.adjacenciesList.append(edge15);
node4.adjacenciesList.append(edge16);
vertexlist = (node1,node2,node3,node4,node5,node6,node7,node8)
calculateshortestpath(vertexlist,node1)
getshortestpath(node7)
Antwoord 9
Ik heb de wikipedia-beschrijving op mijn blog rebrained.com onderverdeeld in de volgende pseudo-code:
Oorspronkelijke status:
- geef knooppunten twee eigenschappen – node.visited en node.distance
- zet node.distance = oneindig voor alle knooppunten behalve startknooppunt op nul
- set node.visited = false voor alle knooppunten
- stel huidig knooppunt in = start knooppunt.
Huidige knooppuntlus:
- als huidig knooppunt = eindknooppunt, voltooi en retourneer current.distance & pad
- bereken voor alle niet-bezochte buren hun voorlopige afstand (current.distance + rand tot buurman).
- indien voorlopige afstand < ingestelde afstand van de buren, overschrijf deze.
- stel current.isvisited = true in.
- stroom instellen = resterende niet-bezochte knoop met kleinste knoop.afstand
import sys
def shortestpath(graph,start,end,visited=[],distances={},predecessors={}):
"""Find the shortest path btw start & end nodes in a graph"""
# detect if first time through, set current distance to zero
if not visited: distances[start]=0
# if we've found our end node, find the path to it, and return
if start==end:
path=[]
while end != None:
path.append(end)
end=predecessors.get(end,None)
return distances[start], path[::-1]
# process neighbors as per algorithm, keep track of predecessors
for neighbor in graph[start]:
if neighbor not in visited:
neighbordist = distances.get(neighbor,sys.maxint)
tentativedist = distances[start] + graph[start][neighbor]
if tentativedist < neighbordist:
distances[neighbor] = tentativedist
predecessors[neighbor]=start
# neighbors processed, now mark the current node as visited
visited.append(start)
# finds the closest unvisited node to the start
unvisiteds = dict((k, distances.get(k,sys.maxint)) for k in graph if k not in visited)
closestnode = min(unvisiteds, key=unvisiteds.get)
# now take the closest node and recurse, making it current
return shortestpath(graph,closestnode,end,visited,distances,predecessors)
if __name__ == "__main__":
graph = {'a': {'w': 14, 'x': 7, 'y': 9},
'b': {'w': 9, 'z': 6},
'w': {'a': 14, 'b': 9, 'y': 2},
'x': {'a': 7, 'y': 10, 'z': 15},
'y': {'a': 9, 'w': 2, 'x': 10, 'z': 11},
'z': {'b': 6, 'x': 15, 'y': 11}}
print shortestpath(graph,'a','a')
print shortestpath(graph,'a','b')
"""
Expected Result:
(0, ['a'])
(20, ['a', 'y', 'w', 'b'])
"""
Antwoord 10
Hier is mijn implementatie van het Dijkstra-algoritme met min-priority-queue. Ik hoop dat je dat ook doet.
from collections import defaultdict
from math import floor
class MinPQ:
"""
each heap element is in form (key value, object handle), while heap
operations works based on comparing key value and object handle points to
the corresponding application object.
"""
def __init__(self, array=[]):
self._minheap = list(array)
self._length = len(array)
self._heapsize = 0
self._build_min_heap()
def _left(self, idx):
return 2*idx+1
def _right(self, idx):
return 2*idx+2
def _parent(self, idx):
return floor((idx-1)/2)
def _min_heapify(self, idx):
left = self._left(idx)
right = self._right(idx)
min_idx = idx
if left <= self._heapsize-1 and self._minheap[left] < self._minheap[min_idx]:
min_idx = left
if right <= self._heapsize-1 and self._minheap[right] < self._minheap[min_idx]:
min_idx = right
if min_idx != idx:
self._minheap[idx], self._minheap[min_idx] = self._minheap[min_idx], self._minheap[idx]
self._min_heapify(min_idx)
def _build_min_heap(self):
self._heapsize = self._length
mid_id = int(self._heapsize-1)-1
for i in range(mid_id, -1, -1):
self._min_heapify(i)
def decrease_key(self, idx, new_key):
while idx > 0 and new_key < self._minheap[self._parent(idx)]:
self._minheap[idx] = self._minheap[self._parent(idx)]
idx = self._parent(idx)
self._minheap[idx] = new_key
def extract_min(self):
minimum = self._minheap[0]
self._minheap[0] = self._minheap[self._heapsize-1]
self._heapsize = self._heapsize - 1
self._min_heapify(0)
return minimum
def insert(self, item):
self._minheap.append(item)
self._heapsize = self._heapsize + 1
self.decrease_key(self._heapsize-1, item)
@property
def minimum(self):
return self._minheap[0]
def is_empty(self):
return self._heapsize == 0
def __str__(self):
return str(self._minheap)
__repr__ = __str__
def __len__(self):
return self._heapsize
class DiGraph:
def __init__(self, edges=None):
self.adj_list = defaultdict(list)
self.add_weighted_edges(edges)
@property
def nodes(self):
nodes = set()
nodes.update(self.adj_list.keys())
for node in self.adj_list.keys():
for neighbor, weight in self.adj_list[node]:
nodes.add(neighbor)
return list(nodes)
def add_weighted_edges(self, edges):
if edges is None:
return None
for edge in edges:
self.add_weighted_edge(edge)
def add_weighted_edge(self, edge):
node1, node2, weight = edge
self.adj_list[node1].append((node2, weight))
def weight(self, tail, head):
for node, weight in self.adj_list[tail]:
if node == head:
return weight
return None
def relax(min_heapq, dist, graph, u, v):
if dist[v] > dist[u] + graph.weight(u, v):
dist[v] = dist[u] + graph.weight(u, v)
min_heapq.insert((dist[v], v))
def dijkstra(graph, start):
# initialize
dist = dict.fromkeys(graph.nodes, float('inf'))
dist[start] = 0
min_heapq = MinPQ()
min_heapq.insert((0, start))
while not min_heapq.is_empty():
distance, u = min_heapq.extract_min()
# we may add a node multiple time in priority queue, but we process it
# only once
if distance > dist[u]:
continue
for neighbor, weight in graph.adj_list[u]:
relax(min_heapq, dist, graph, u, neighbor)
return dist
if __name__ == "__main__":
edges = [('s', 't', 10), ('t', 'x', 1), ('s', 'y', 5), ('y', 't', 3), ('t', 'y', 2),
('y', 'x', 9), ('y', 'z', 2), ('z', 's', 7), ('x', 'z', 4), ('z', 'x', 6)]
digraph = DiGraph(edges)
res = dijkstra(digraph, 's')
print(res)
Antwoord 11
Ik implementeer Dijkstra met behulp van priority-queue. Daarnaast implementeer ik zelf ook min-heap. Ik hoop dat dit je zal helpen.
from collections import defaultdict
class MinPQ:
"""
each heap element is in form (key value, object handle), while heap
operations works based on comparing key value and object handle points to
the corresponding application object.
"""
def __init__(self, array=[]):
self._minheap = list(array)
self._length = len(array)
self._heapsize = 0
self._build_min_heap()
def _left(self, idx):
return 2*idx+1
def _right(self, idx):
return 2*idx+2
def _parent(self, idx):
return int((idx-1)/2)
def _min_heapify(self, idx):
left = self._left(idx)
right = self._right(idx)
min_idx = idx
if left <= self._heapsize-1 and self._minheap[left] < self._minheap[min_idx]:
min_idx = left
if right <= self._heapsize-1 and self._minheap[right] < self._minheap[min_idx]:
min_idx = right
if min_idx != idx:
self._minheap[idx], self._minheap[min_idx] = self._minheap[min_idx], self._minheap[idx]
self._min_heapify(min_idx)
def _build_min_heap(self):
self._heapsize = self._length
mid_id = int((self._heapsize)/2)-1
for i in range(mid_id, -1, -1):
self._min_heapify(i)
def decrease_key(self, idx, new_key):
while idx > 0 and new_key < self._minheap[self._parent(idx)]:
self._minheap[idx] = self._minheap[self._parent(idx)]
idx = self._parent(idx)
self._minheap[idx] = new_key
def extract_min(self):
if self._heapsize < 1:
raise IndexError
minimum = self._minheap[0]
self._minheap[0] = self._minheap[self._heapsize-1]
self._heapsize = self._heapsize - 1
self._min_heapify(0)
return minimum
def insert(self, item):
self._minheap.append(item)
self._heapsize = self._heapsize + 1
self.decrease_key(self._heapsize-1, item)
@property
def minimum(self):
return self._minheap[0]
def is_empty(self):
return self._heapsize == 0
def __str__(self):
return str(self._minheap)
__repr__ = __str__
def __len__(self):
return self._heapsize
class DiGraph:
def __init__(self, edges=None):
self.adj_list = defaultdict(list)
self.add_weighted_edges(edges)
@property
def nodes(self):
nodes = set()
nodes.update(self.adj_list.keys())
for node in self.adj_list.keys():
for neighbor, weight in self.adj_list[node]:
nodes.add(neighbor)
return list(nodes)
def add_weighted_edges(self, edges):
if edges is None:
return None
for edge in edges:
self.add_weighted_edge(edge)
def add_weighted_edge(self, edge):
node1, node2, weight = edge
self.adj_list[node1].append((node2, weight))
def weight(self, tail, head):
for node, weight in self.adj_list[tail]:
if node == head:
return weight
return None
def relax(min_heapq, dist, graph, u, v):
if dist[v] > dist[u] + graph.weight(u, v):
dist[v] = dist[u] + graph.weight(u, v)
min_heapq.insert((dist[v], v))
def dijkstra(graph, start):
# initialize
dist = dict.fromkeys(graph.nodes, float('inf'))
dist[start] = 0
min_heapq = MinPQ()
min_heapq.insert((0, start))
while not min_heapq.is_empty():
distance, u = min_heapq.extract_min()
# we may add a node multiple time in priority queue, but we process it
# only once
if distance > dist[u]:
continue
for neighbor, weight in graph.adj_list[u]:
relax(min_heapq, dist, graph, u, neighbor)
return dist