dijkstra

#---------- Lezione 18.1 -----------
# Grafo pesato rappresentati con matrice di adiacenza
# Algoritmo di Dijkstra

inf = float("inf")

def createGraph(n):
    M = []
    for i in range(n):
        M.append([])
        for j in range(n):
            M[i].append(inf)
    return M

def size(G):  #restituisce i nodi
    return len(G)

def printGraph(G):
    for i in range(len(G)):
        print(G[i])             # theta(n)

def insert(G,i,j,w):
    G[i][j] = w

def delete(G,i,j):            # theta(1)
    G[i][j] = inf

def isEdge(G,i,j):
    return G[i][j] != inf

def weight(G,i,j):
    return G[i][j]

def outDegree(G,i):
    s = 0;
    for j in range(len(G)):
        if G[i][j] != inf:
            s = s + 1
    return s

def InDegree(G,j):
    s = 0;
    for i in range(len(G)):
        if G[i][j] != inf:
            s = s + 1
    return s

def neighbors(G,i):
    V = []
    for j in range(len(G)):
        if G[i][j] != inf:
            V.append([ j, G[i][j] ])
    return V

#---------- Programma principale ------------

G = createGraph(6)
printGraph(G)
insert(G, 0, 1, 2)
insert(G, 0, 5, 9)
insert(G, 1, 3, 8)
insert(G, 1, 2, 6)
insert(G, 1, 5, 5)
insert(G, 2, 3, 1)
insert(G, 4, 3, 3)
insert(G, 4, 2, 7)
insert(G, 5, 4, 3)
printGraph(G)

def minVertex(D,V):
    mindistance = inf
    nodo = -1

    for i in range(len(D)):
        if (not V[i]) and (D[i] < mindistance):
            nodo = i
            mindistance = D[i]

    return nodo

def Dijkstra(G,s):
    #preparo variabili
    n = size(G)
    dist = []
    pred = []
    visited = []

    #impostazione per inizio algoritmo
    for i in range(n):
        dist.append(inf)
        visited.append(False)
        pred.append(-1)

    #imposto a 0 perchè è il mio punto di partenza
    dist[s] = 0

    for i in range(n-1):
        next = minVertex(dist,visited)
        visited[next] = True
        V = neighbors(G,next)
        for [z,w] in V:
            d = dist[next] + w
            if (dist[z] > d):
                #fase di rilassamento
                dist[z] = d
                pred[z] = next

    return [dist, pred]

D = Dijkstra(G,0)
print("")
print(D[0])
print(D[1])