Z10-Rešenja

Functions

# file: 'functions.py'
import sys
from graph import *
from math import inf
from random import randint

def create_graph():
x = Vertex("x")
y = Vertex("y")
z = Vertex("z")
s = Vertex("s")
t = Vertex("t")

V = [s, x, y, z, t]
E = []

E.append(Edge(s, y, 5))
E.append(Edge(s, t, 10))

E.append(Edge(y, t, 3))
E.append(Edge(y, z, 2))
E.append(Edge(y, x, 9))

E.append(Edge(z, s, 7))
E.append(Edge(z, x, 6))

E.append(Edge(x, z, 4))

E.append(Edge(t, x, 1))

E.append(Edge(t, y, 2))

return Graph(V, E)

def initialize_single_source(G, s):
for v in G.V:
v.d = inf
v.p = None
s.d = 0

def extract_min(V):
m = V[0]
for v in V:
if v.d < m.d:
m = v
V.remove(m)
return m

def relax(u, v, G):
if v.d > u.d + G.get_edge_value(u, v):
v.d = u.d + G.get_edge_value(u, v)
v.p = u

def dijkstra(G, s):
initialize_single_source(G, s)
S = []
Q = G.V[:]
while Q:
u = extract_min(Q)
S.append(u)
for v in G.get_neighbours(u):
relax(u, v, G)

def print_path(G, s, v):
if v == s:
print(s.val, end=" ")
elif v.p == None:
print ("no path found from", s.val, "to", v.val, "exists")
else:
print_path(G, s, v.p)
print(v.val, end=" ")

def generate_graph(n, m, edge):
N = n
G = Graph()
for i in range(N):

for i in range(N):
for j in range(randint(1, m)):
r = i
while r == i:
r = randint(0, N - 1)
return G


functions.py

Graph

# file: 'graph.py'
import sys

class Vertex:
def __init__(self, val):
self.val = val

class Edge:
def __init__(self, u, v, val):
self.first = u
self.second = v
self.val = val

class Graph:
def __init__(self, V=[], E=[]):
self.V = V
self.E = E

self.V.append(v)

self.E.append(edge)

def get_neighbours(self, v):
L = []
for i in self.E:
if i.first == v:
L.append(i.second)
return L

def get_edge_value(self, u, v):
for i in self.E:
if i.first == u and i.second == v:
return i.val
return inf

def __str__(self):
return "Nodes: " + str([f"{i.val}" for i in self.V]) + "\nConnections: " + str([f"({i.first.val}, {i.second.val}, {i.val})" for i in self.E])


graph.py

# file: 'z10-1.py'
import sys
from functions import *

if __name__ == "__main__":
print("PREDEFINED GRAPH")
G = create_graph()

s = G.V[0]
dijkstra(G, s)

for v in G.V:
print("Path", s.val, "->", v.val, ":")
print_path(G, s, v)
print(v.d)
print()

print("RANDOM GENERATED GRAPH")
G = generate_graph(5, 5, 10)
s = G.V[0]

print(G)

dijkstra(G, s)

for v in G.V:
print("Path", s.val, "->", v.val, ":")
print_path(G, s, v)
print()
print("Total distance: ", v.d)
print()