cs215 ยป

CS215 Unit 5

# CS215Unit5Code

Code for 11: Code for Dijkstra

``````def shortest_dist_node(dist):
best_node = 'undefined'
best_value = 100000
for v in dist:
if dist[v] < best_value:
(best_node, best_value) = (v, dist[v])
return best_node

def dijkstra(G,v):
dist_so_far = {}
dist_so_far[v] = 0
final_dist = {}
while len(final_dist) < len(G):
w = shortest_dist_node(dist_so_far)
# lock it down!
final_dist[w] = dist_so_far[w]
del dist_so_far[w]
for x in G[w]:
if x not in final_dist:
new_dist = final_dist[w] + G[w][x]
if (x not in dist_so_far) or (new_dist < dist_so_far[x]):
dist_so_far[x] = new_dist
return final_dist
``````

Code for 19: Bounds on the Estimate

``````import random

if node1 not in G:
G[node1] = {}
(G[node1])[node2] = 1
if node2 not in G:
G[node2] = {}
(G[node2])[node1] = 1
return G

flights = [(1,2),(1,3),(2,3),(2,6),(2,4),(2,5),(3,6),(4,5)]
G = {}

def clustering_coefficient(G,v):
neighbors = G[v].keys()
if len(neighbors) == 1: return 0.0
for w in neighbors:
for u in neighbors:
if u in G[w]: links += 0.5

v = 2
print "CC:", clustering_coefficient(G,v)

vindex = {}
d = 0
for w in G[v].keys():
vindex[d] = w
d += 1

total = 0
for i in range(1,1000):
if d > 1:
pick = random.randint(0,d-1)
v1 = vindex[pick]
v2 = vindex[(pick+random.randint(1,d-1))%d]
if v2 in G[v1]: total += 1
print i, (total+0.0)/i
``````