Z10-Rešenja

Table of Contents

  1. Functions
  2. Graph
  3. Zadatak 1

Functions

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
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):
        G.add_vertex(Vertex(i))

    for i in range(N):
        for j in range(randint(1, m)):
            r = i
            while r == i:
                r = randint(0, N - 1)
            G.add_edge(Edge(G.V[i], G.V[r], randint(0, edge)))
    return G

functions.py

Graph

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
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

    def add_vertex(self, v):
        self.V.append(v)

    def add_edge(self, edge):
        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

Zadatak 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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()

zadatak1.py