bellman.py

import pdb
"""
Algoritmul Bellman-Ford

Explicatii:

    iter(graph) returneaza toate nodurile
    iter(graph[u]) returneaza nodul vecin lui u
    graph[u][v] returneaza ponderea muchiei (u, v)
"""

# Pasul 1: Pentru fiecare nod pregatim destinatia si predecesorul
def initialize(graph, source):
    d = {} # destinatie
    p = {} # predecesor
    for node in graph:
        d[node] = float('Inf') # presupunem ca nodurile sunt foarte departe unele de altele
        p[node] = None
    d[source] = 0 # distanta pana la sursa este cunoscuta, e 0
    return d, p

def relax(node, neighbour, graph, d, p):
    # daca distanta dintre nod si vecinul sau e mai mica decat ce avem pana acum
    if d[neighbour] > d[node] + graph[node][neighbour]:
        # inregistram aceasta distanat mai mica
        d[neighbour]  = d[node] + graph[node][neighbour]
        p[neighbour] = node

def bellman_ford(graph, source):
    d, p = initialize(graph, source)
    for i in range(len(graph)-1): #Rulam secventa de mai jos pana la convergenta, N-1 (numarul de noduri)
        for u in graph:
            for v in graph[u]: #Pentru fiecare vecin al lui u
                relax(u, v, graph, d, p) #"Relaxam" distantele

    # Pasul 3: verificam daca nu avem cicluri cu muchii negative
    for u in graph:
        for v in graph[u]:
            assert d[v] <= d[u] + graph[u][v]

    return d, p


def test():
    graph = {
        'a': {'b': -1, 'c':  4},
        'b': {'c':  3, 'd':  2, 'e':  2},
        'c': {},
        'd': {'b':  1, 'c':  5},
        'e': {'d': -3}
        }

    d, p = bellman_ford(graph, 'a')

    assert d == {
        'a':  0,
        'b': -1,
        'c':  2,
        'd': -2,
        'e':  1
        }

    assert p == {
        'a': None,
        'b': 'a',
        'c': 'b',
        'd': 'e',
        'e': 'b'
        }

if __name__ == '__main__': test()