# Cod sursa(job #1152881)

Utilizator Data 25 martie 2014 03:58:24 Algoritmul lui Dijkstra 0 py done Arhiva educationala 5.86 kb
``````import argparse, math, sys
from Queue import PriorityQueue

# PART A: Fill in below the code for disjktra
def dijkstra(G, source):
n = G.get_size()[0]
d = [float("inf")] * n
p = [-1] * n
d[source] = 0

q = Heap(n)

q.decrease_value(source, d[source])
while q.size() > 0:
x = q.extract_min()
for y, dst in G.get_neighbors(x):
if d[y] > d[x] + dst:
d[y] = d[x] + dst
p[y] = x
q.decrease_value(y, d[y])

return (d, p)

# PART B: Fill in below the code for part b
def find_path(G, plant, dump):
(d, p) = dijkstra(G, plant)

path = []
q = dump
while q != plant:
path.append(q)
q = p[q]
path = path.reverse()

return (d[dump], path)

# PART C: Fill in below the code for part c
def get_closest_k(G, plant, dumps, k):
(d, p) = disjkstra(G, plant)

dump_d = []
for dump in dumps:
dump_d.append((d[dump], dump))

dump_d = sorted(dump_d)

res = []
for i in range(k):
res.append(dump_d[i][1])

return res

# PART D: Fill in below the code for part d
def find_path_least_waste(G, plant, dump):
# Create new graph
N, M = G.get_size()
edges = G.get_edges()
for i in range(M):
edges[i][2] = math.log(edges[i][2])

G_new = Graph(N, edges)

return find_path(G_new, plant, dump)

######################################
# DO NOT CHANGE CODE BELOW THIS LINE #
######################################

class Graph:
def __init__(self, N_nodes, edges):
"""
Given the number of nodes and the set of edges instantiates a Graph object.

Args:
N_nodes: an integer with the number of nodes in the graph
edges: a list of edges in tuple format (x, y, dist) representing an edge from x to y of lenght dist
"""

self.N_nodes = N_nodes
self.edges = edges
self.neighbors = [[] for i in range(N_nodes)]

# Create neighbors
for i in range(len(edges)):
self.neighbors[edges[i][0]].append((edges[i][1], edges[i][2]))

def get_size(self):
"""
Returns the size of the graph as a tuple (number_of_nodes, number_of_edges)

Args:
None

Returns:
A tuple (number_of_nodes, number_of_edges)
"""
return (self.N_nodes, len(self.edges))

def get_edges(self):
"""
Returns the edges in the graph in tuple form: for edge x->y the tuples is (x, y, distance)

Args:
None

Returns:
A list of tuples [(x, y, distance), ...]
"""
return self.edges

def get_neighbors(self, node):
"""
Given a node returns the neighbors of that node and the corresponding distance to them

Args:
node: the node to be given the neighbors of

Returns:
A list of tuples [(y, distance), ...] where y is a neighbor of x and distance is the distance from x to y
"""
return self.neighbors[node]

class Heap:
def __init__(self, N_nodes):
self.N = N_nodes
self.heap = [0] + [(float("inf"), i) for i in range(N_nodes)]
self.pos = [i+1 for i in range(N_nodes)]

def size(self):
return self.N
def val_at(self, i):
return self.heap[i][0]
def node_at(self, i):
return self.heap[i][1]
def where_is(self, node):
return self.pos[node]
def swap(self, i, j):
self.heap[i], self.heap[j] = self.heap[j], self.heap[i]
self.pos[self.node_at(i)] = i
self.pos[self.node_at(j)] = j

def heapify_down(self, i):
if i > self.N:
return None

f1 = 2 * i
f2 = 2 * i + 1

lowest = i

if f1 <= self.N and self.val_at(f1) < self.val_at(lowest):
lowest = f1
if f2 <= self.N and self.val_at(f2) < self.val_at(lowest):
lowest = f2

if lowest != i:
self.swap(i, lowest)
self.heapify_down(lowest)

def heapify_up(self, i):
if i <= 1:
return None

if self.val_at(i) < self.val_at(i // 2):
self.swap(i, i // 2)
self.heapify_up(i // 2)

def decrease_value(self, node, new_val):
i = self.where_is(node)
if not (1 <= i and i <= self.N):
print "You are trying to decrease value of a node that does not exist anymore"
sys.exit()
if new_val < self.val_at(i):
self.heap[i] = (new_val, self.heap[i][1])
self.heapify_up(i)

def extract_min(self):
node = self.heap[1][1]
self.pos[node] = -1

self.heap[1] = self.heap[self.N]
self.pos[self.heap[1][1]] = 1
self.N -= 1
self.heapify_down(1)

return node

def run_from_file(input_file):
f = open(input_file)
f.close()

# get graph
N = int(lines[0].rstrip().split(" ")[0])
M = int(lines[0].rstrip().split(" ")[1])
edges = []
for i in range(1, M + 1):
s = lines[i].rstrip().split(" ")
edges.append((int(s[0]), int(s[1]), int(s[2])))

G = Graph(N, edges)

(d, p) = dijkstra(G, 0)

print d
print p

def run_for_infoarena():
f = open("dijkstra.in")
f.close()

# get graph
N = int(lines[0].rstrip().split(" ")[0])
M = int(lines[0].rstrip().split(" ")[1])
edges = []
for i in range(1, M + 1):
s = lines[i].rstrip().split(" ")
edges.append((int(s[0]) - 1, int(s[1]) - 1, int(s[2])))

G = Graph(N, edges)

(d, p) = dijkstra(G, 0)

g = open("dijkstra.out", "w")

for i in range(1, N):
g.write(str(d[i]) + " ")

g.write("\n")
g.close()

if __name__ == '__main__':
#import argparse, cProfile
#parser = argparse.ArgumentParser()