Resumos

Dijkstra(G(V,E), w, x):
    for v in V:
        v.d = infinito
        v.pi = null
    x.d = 0

    S = {}
    Q = V

    while(!Q.empty):
        u = ExtractMin(Q)
        S = S UNIONE {u}

        for v in adj(u):
            if v.d > u.d + w(u,v):
                v.d = u.d + w(u,v)
                v.pi = u

Ogni nodo v ha due attributi:

• v.d = lunghezza del cammino minimo verso v
• v.pi = nodo predecessore di v

L'algoritmo mantiene due insiemi:

• S = insieme dei nodi visitati (per i quali il cammino minimo è stato calcolato)
• Q = insieme dei nodi non ancora visitati

Funzioni di utilità:

• w(u,v) = restituisce il peso dell'arco (u,v)
• adj(u) = restituisce i nodi adiacenti a u
• ExtractMin(Q) = estrae da Q il nodo u con valore u.d più piccolo

for v in V:
    v.d = infinito
    v.pi = null
x.d = 0

S = {}
Q = V

Fase di inizializzazione:

• v.d = infinito (nessun nodo è stato ancora raggiunto) e v.pi = null (nessun nodo ha un predecessore)
• x.d = 0 (il nodo sorgente ha distanza 0 da sé stesso)
• S = {} (nessun nodo è stato visitato) e Q = V (tutti i nodi sono ancora da visitare)

while(!Q.empty):
    u = ExtractMin(Q)
    S = S UNIONE {u}

    for v in adj(u):
        if v.d > u.d + w(u,v):
            v.d = u.d + w(u,v)
            v.pi = u

Esempio

Trovare il cammino minimo dal nodo X al nodo Y.

Una semplice BFS/DFS non basta. Nel grafo non sono presenti archi con peso negativo: possiamo usare Dijkstra.

• fase di inizializzazione, creazione di S e Q:

  

• iterazione:

  • nodo con d minimo in Q: X
  • aggiungo X ad S
  • aggiorno d degli adiacenti di X
  • aggiorno pi degli adiacenti di X

  

• iterazione:

  • nodo con d minimo in Q: A
  • aggiungo A ad S
  • aggiorno d degli adiacenti di A
  • aggiorno pi degli adiacenti di A

  

• iterazione:

  • nodo con d minimo in Q: B
  • aggiungo B ad S
  • aggiorno d degli adiacenti di B
  • aggiorno pi degli adiacenti di B

  

• iterazione:

  • nodo con d minimo in Q: D
  • aggiungo D ad S
  • aggiorno d degli adiacenti di D
  • aggiorno pi degli adiacenti di D

  

• iterazione:

  • nodo con d minimo in Q: C
  • aggiungo C ad S
  • aggiorno d degli adiacenti di C
  • aggiorno pi degli adiacenti di C

  

• iterazione:

  • nodo con d minimo in Q: E
  • aggiungo E ad S
  • aggiorno d degli adiacenti di E
  • aggiorno pi degli adiacenti di E

  

• iterazione:

  • nodo con d minimo in Q: F
  • aggiungo F ad S
  • aggiorno d degli adiacenti di F
  • aggiorno pi degli adiacenti di F

  

• iterazione:

  • nodo con d minimo in Q: G
  • aggiungo G ad S
  • aggiorno d degli adiacenti di G
  • aggiorno pi degli adiacenti di G

  

• iterazione:

  • nodo con d minimo in Q: Y
  • aggiungo Y ad S
  • aggiorno d degli adiacenti di Y
  • aggiorno pi degli adiacenti di Y

  

• STOP!

  • Q è adesso vuota
  • Il costo del cammino minimo da X a Y è pari a 6.