def dijkstra(adj, costs, s, t):
''' Return predecessors and min distance if there exists a shortest path
from s to t; Otherwise, return None '''
Q = [] # priority queue of items; note item is mutable.
d = {s: 0} # vertex -> minimal distance
Qd = {} # vertex -> [d[v], parent_v, v]
p = {} # predecessor
visited_set = set([s])
for v in adj.get(s, []):
d[v] = costs[s, v]
item = [d[v], s, v]
heapq.heappush(Q, item)
Qd[v] = item
while Q:
print Q
cost, parent, u = heapq.heappop(Q)
if u not in visited_set:
print 'visit:', u
p[u]= parent
visited_set.add(u)
if u == t:
return p, d[u]
for v in adj.get(u, []):
if d.get(v):
if d[v] > costs[u, v] + d[u]:
d[v] = costs[u, v] + d[u]
Qd[v][0] = d[v] # decrease key
Qd[v][1] = u # update predecessor
heapq._siftdown(Q, 0, Q.index(Qd[v]))
else:
d[v] = costs[u, v] + d[u]
item = [d[v], u, v]
heapq.heappush(Q, item)
Qd[v] = item
return None
python类_siftdown()的实例源码
def getSkyline(self, buildings):
"""
:type buildings: List[List[int]]
:rtype: List[List[int]]
"""
hs = []
heap = []
for b in buildings:
hs.append((b[0], -b[2]))
hs.append((b[1], b[2]))
hs.sort()
ans = []
pre = cur = None
for h in hs:
pos = h[0]
height = h[1]
if height < 0:
heapq.heappush(heap, height)
else:
i = heap.index(-height)
heap[i] = heap[-1]
heap.pop()
if i < len(heap):
heapq._siftup(heap, i)
heapq._siftdown(heap, 0, i)
if heap:
cur = heap[0]
if cur != pre:
ans.append((pos, -1 * cur))
pre = cur
else:
ans.append((pos, 0))
return ans
def pop(self):
# Will remove item from the heap.
value = heapq.heappop(self.heap)
if self.max:
value *= -1
return value
# def delete(self, index):
# # Magic heapify.
# self.heap[index] = self.heap[-1] # Move root to index i.
# self.heap.pop() # pop() last element in array O(1).
# if index < len(self.heap): # Need to sift things.
# # Magical internal heapify functions that does stuff in log n.
# heapq._siftup(self.heap, index)
# heapq._siftdown(self.heap, 0, index)
def _rank_cycle_function(self, cycle, function, ranks):
"""Dijkstra's shortest paths algorithm.
See also:
- http://en.wikipedia.org/wiki/Dijkstra's_algorithm
"""
import heapq
Q = []
Qd = {}
p = {}
visited = set([function])
ranks[function] = 0
for call in compat_itervalues(function.calls):
if call.callee_id != function.id:
callee = self.functions[call.callee_id]
if callee.cycle is cycle:
ranks[callee] = 1
item = [ranks[callee], function, callee]
heapq.heappush(Q, item)
Qd[callee] = item
while Q:
cost, parent, member = heapq.heappop(Q)
if member not in visited:
p[member]= parent
visited.add(member)
for call in compat_itervalues(member.calls):
if call.callee_id != member.id:
callee = self.functions[call.callee_id]
if callee.cycle is cycle:
member_rank = ranks[member]
rank = ranks.get(callee)
if rank is not None:
if rank > 1 + member_rank:
rank = 1 + member_rank
ranks[callee] = rank
Qd_callee = Qd[callee]
Qd_callee[0] = rank
Qd_callee[1] = member
heapq._siftdown(Q, 0, Q.index(Qd_callee))
else:
rank = 1 + member_rank
ranks[callee] = rank
item = [rank, member, callee]
heapq.heappush(Q, item)
Qd[callee] = item
def _rank_cycle_function(self, cycle, function, ranks):
"""Dijkstra's shortest paths algorithm.
See also:
- http://en.wikipedia.org/wiki/Dijkstra's_algorithm
"""
import heapq
Q = []
Qd = {}
p = {}
visited = set([function])
ranks[function] = 0
for call in compat_itervalues(function.calls):
if call.callee_id != function.id:
callee = self.functions[call.callee_id]
if callee.cycle is cycle:
ranks[callee] = 1
item = [ranks[callee], function, callee]
heapq.heappush(Q, item)
Qd[callee] = item
while Q:
cost, parent, member = heapq.heappop(Q)
if member not in visited:
p[member]= parent
visited.add(member)
for call in compat_itervalues(member.calls):
if call.callee_id != member.id:
callee = self.functions[call.callee_id]
if callee.cycle is cycle:
member_rank = ranks[member]
rank = ranks.get(callee)
if rank is not None:
if rank > 1 + member_rank:
rank = 1 + member_rank
ranks[callee] = rank
Qd_callee = Qd[callee]
Qd_callee[0] = rank
Qd_callee[1] = member
heapq._siftdown(Q, 0, Q.index(Qd_callee))
else:
rank = 1 + member_rank
ranks[callee] = rank
item = [rank, member, callee]
heapq.heappush(Q, item)
Qd[callee] = item
def _rank_cycle_function(self, cycle, function, ranks):
"""Dijkstra's shortest paths algorithm.
See also:
- http://en.wikipedia.org/wiki/Dijkstra's_algorithm
"""
import heapq
Q = []
Qd = {}
p = {}
visited = set([function])
ranks[function] = 0
for call in compat_itervalues(function.calls):
if call.callee_id != function.id:
callee = self.functions[call.callee_id]
if callee.cycle is cycle:
ranks[callee] = 1
item = [ranks[callee], function, callee]
heapq.heappush(Q, item)
Qd[callee] = item
while Q:
cost, parent, member = heapq.heappop(Q)
if member not in visited:
p[member]= parent
visited.add(member)
for call in compat_itervalues(member.calls):
if call.callee_id != member.id:
callee = self.functions[call.callee_id]
if callee.cycle is cycle:
member_rank = ranks[member]
rank = ranks.get(callee)
if rank is not None:
if rank > 1 + member_rank:
rank = 1 + member_rank
ranks[callee] = rank
Qd_callee = Qd[callee]
Qd_callee[0] = rank
Qd_callee[1] = member
heapq._siftdown(Q, 0, Q.index(Qd_callee))
else:
rank = 1 + member_rank
ranks[callee] = rank
item = [rank, member, callee]
heapq.heappush(Q, item)
Qd[callee] = item
def _rank_cycle_function(self, cycle, function, ranks):
"""Dijkstra's shortest paths algorithm.
See also:
- http://en.wikipedia.org/wiki/Dijkstra's_algorithm
"""
import heapq
Q = []
Qd = {}
p = {}
visited = set([function])
ranks[function] = 0
for call in compat_itervalues(function.calls):
if call.callee_id != function.id:
callee = self.functions[call.callee_id]
if callee.cycle is cycle:
ranks[callee] = 1
item = [ranks[callee], function, callee]
heapq.heappush(Q, item)
Qd[callee] = item
while Q:
cost, parent, member = heapq.heappop(Q)
if member not in visited:
p[member]= parent
visited.add(member)
for call in compat_itervalues(member.calls):
if call.callee_id != member.id:
callee = self.functions[call.callee_id]
if callee.cycle is cycle:
member_rank = ranks[member]
rank = ranks.get(callee)
if rank is not None:
if rank > 1 + member_rank:
rank = 1 + member_rank
ranks[callee] = rank
Qd_callee = Qd[callee]
Qd_callee[0] = rank
Qd_callee[1] = member
heapq._siftdown(Q, 0, Q.index(Qd_callee))
else:
rank = 1 + member_rank
ranks[callee] = rank
item = [rank, member, callee]
heapq.heappush(Q, item)
Qd[callee] = item
def _rank_cycle_function(self, cycle, function, ranks):
"""Dijkstra's shortest paths algorithm.
See also:
- http://en.wikipedia.org/wiki/Dijkstra's_algorithm
"""
import heapq
Q = []
Qd = {}
p = {}
visited = set([function])
ranks[function] = 0
for call in compat_itervalues(function.calls):
if call.callee_id != function.id:
callee = self.functions[call.callee_id]
if callee.cycle is cycle:
ranks[callee] = 1
item = [ranks[callee], function, callee]
heapq.heappush(Q, item)
Qd[callee] = item
while Q:
cost, parent, member = heapq.heappop(Q)
if member not in visited:
p[member]= parent
visited.add(member)
for call in compat_itervalues(member.calls):
if call.callee_id != member.id:
callee = self.functions[call.callee_id]
if callee.cycle is cycle:
member_rank = ranks[member]
rank = ranks.get(callee)
if rank is not None:
if rank > 1 + member_rank:
rank = 1 + member_rank
ranks[callee] = rank
Qd_callee = Qd[callee]
Qd_callee[0] = rank
Qd_callee[1] = member
heapq._siftdown(Q, 0, Q.index(Qd_callee))
else:
rank = 1 + member_rank
ranks[callee] = rank
item = [rank, member, callee]
heapq.heappush(Q, item)
Qd[callee] = item
def _rank_cycle_function(self, cycle, function, ranks):
"""Dijkstra's shortest paths algorithm.
See also:
- http://en.wikipedia.org/wiki/Dijkstra's_algorithm
"""
import heapq
Q = []
Qd = {}
p = {}
visited = set([function])
ranks[function] = 0
for call in compat_itervalues(function.calls):
if call.callee_id != function.id:
callee = self.functions[call.callee_id]
if callee.cycle is cycle:
ranks[callee] = 1
item = [ranks[callee], function, callee]
heapq.heappush(Q, item)
Qd[callee] = item
while Q:
cost, parent, member = heapq.heappop(Q)
if member not in visited:
p[member]= parent
visited.add(member)
for call in compat_itervalues(member.calls):
if call.callee_id != member.id:
callee = self.functions[call.callee_id]
if callee.cycle is cycle:
member_rank = ranks[member]
rank = ranks.get(callee)
if rank is not None:
if rank > 1 + member_rank:
rank = 1 + member_rank
ranks[callee] = rank
Qd_callee = Qd[callee]
Qd_callee[0] = rank
Qd_callee[1] = member
heapq._siftdown(Q, 0, Q.index(Qd_callee))
else:
rank = 1 + member_rank
ranks[callee] = rank
item = [rank, member, callee]
heapq.heappush(Q, item)
Qd[callee] = item
def _rank_cycle_function(self, cycle, function, ranks):
"""Dijkstra's shortest paths algorithm.
See also:
- http://en.wikipedia.org/wiki/Dijkstra's_algorithm
"""
import heapq
Q = []
Qd = {}
p = {}
visited = set([function])
ranks[function] = 0
for call in compat_itervalues(function.calls):
if call.callee_id != function.id:
callee = self.functions[call.callee_id]
if callee.cycle is cycle:
ranks[callee] = 1
item = [ranks[callee], function, callee]
heapq.heappush(Q, item)
Qd[callee] = item
while Q:
cost, parent, member = heapq.heappop(Q)
if member not in visited:
p[member]= parent
visited.add(member)
for call in compat_itervalues(member.calls):
if call.callee_id != member.id:
callee = self.functions[call.callee_id]
if callee.cycle is cycle:
member_rank = ranks[member]
rank = ranks.get(callee)
if rank is not None:
if rank > 1 + member_rank:
rank = 1 + member_rank
ranks[callee] = rank
Qd_callee = Qd[callee]
Qd_callee[0] = rank
Qd_callee[1] = member
heapq._siftdown(Q, 0, Q.index(Qd_callee))
else:
rank = 1 + member_rank
ranks[callee] = rank
item = [rank, member, callee]
heapq.heappush(Q, item)
Qd[callee] = item
def _rank_cycle_function(self, cycle, function, ranks):
"""Dijkstra's shortest paths algorithm.
See also:
- http://en.wikipedia.org/wiki/Dijkstra's_algorithm
"""
import heapq
Q = []
Qd = {}
p = {}
visited = set([function])
ranks[function] = 0
for call in compat_itervalues(function.calls):
if call.callee_id != function.id:
callee = self.functions[call.callee_id]
if callee.cycle is cycle:
ranks[callee] = 1
item = [ranks[callee], function, callee]
heapq.heappush(Q, item)
Qd[callee] = item
while Q:
cost, parent, member = heapq.heappop(Q)
if member not in visited:
p[member]= parent
visited.add(member)
for call in compat_itervalues(member.calls):
if call.callee_id != member.id:
callee = self.functions[call.callee_id]
if callee.cycle is cycle:
member_rank = ranks[member]
rank = ranks.get(callee)
if rank is not None:
if rank > 1 + member_rank:
rank = 1 + member_rank
ranks[callee] = rank
Qd_callee = Qd[callee]
Qd_callee[0] = rank
Qd_callee[1] = member
heapq._siftdown(Q, 0, Q.index(Qd_callee))
else:
rank = 1 + member_rank
ranks[callee] = rank
item = [rank, member, callee]
heapq.heappush(Q, item)
Qd[callee] = item
