Algoritmo Dijkstra in un digrafo ciclico con archi negativi

Quando un digrafo contiene archi negativi, potrebbero esserci dei cicli ( loop ) che vanificano il funzionamento dell'algoritmo di Dijkstra.

Soluzione

Per evitare questo rischio aggiungo un ulteriore controllo all'algoritmo.

1. Calcolo il costo minimo negativo (c_min) ossia il valore dell'arco con il costo negativo più basso.
2. Verifico se la seguente condizione non è soddisfatta per ciascun nodo $$ d_j<(n-1)c_{min} $$

Questa condizione è soddisfatta in presenza di un ciclo nel grafo orientato.

Nota. La variabile d_j è il costo del cammino fino al nodo di destinazione j. La variabile n indica il numero dei nodi nel digrafo.

Esempio

Questo grafo è composto da n=4 nodi e m=5 archi.

C'è un arco negativo dal nodo 1 al nodo s che causa un ciclo.

Si tratta del ciclo 0→2→1→0

Attenzione. La presenza degli archi negativi non necessariamente determina un ciclo. E' opportuno ricordarlo perché spesso ci si confonde.

In questo caso l'algoritmo di Dijkstra entra in un loop infinito.

• nodo s
  c'è un solo arco in uscita verso il nodo 2 che costa +1
• nodo 2
  ci sono due archi in uscita verso i nodi 1 e t.
  • l'arco verso il nodo 1 costa +1
  • l'arco verso il nodo t costa +2
  l'algoritmo sceglie il nodo 1 perché costa meno
• nodo 1
  ci sono due archi in uscita verso i nodi s e t.
  • l'arco verso il nodo s costa -5
  • l'arco verso il nodo t costa +1
  l'algoritmo sceglie il nodo s perché costa meno. E comincia un loop infinito.

La soluzione

Al momento dell'inizializzazione dell'algoritmo cerco il costo negativo minimo nel digrafo.

E' l'arco dal nodo 1 al nodo s con costo -5.

$$ c_{min} = -5 $$

Durante l'esecuzione dell'algoritmo di Dijkstra verifico se la seguente condizione è soddisfatta oppure no.

$$ d_j<(n-1)c_{min} $$

$$ d_j<(4-1) \cdot (-5) $$

$$ d_j<(3) \cdot (-5) $$

$$ d_j<-15 $$

Ora l'algoritmo di Dijkstra individua la presenza del ciclo e si blocca.

• nodo s
  c'è un solo arco in uscita verso il nodo 2 che costa +1
  d₂=0+1=1
  d₂<-15 ? no
• nodo 2
  ci sono due archi in uscita verso i nodi 1 e t.
  • l'arco verso il nodo 1 costa +1
  • l'arco verso il nodo t costa +2
  l'algoritmo sceglie il nodo 1 perché costa meno
  d₁=1+1=2
  d₁<-15 ? no
• nodo 1
  ci sono due archi in uscita verso i nodi s e t.
  • l'arco verso il nodo s costa -5
  • l'arco verso il nodo t costa +1
  l'algoritmo sceglie il nodo s perché costa meno.
  d_s=2-5=-3
  d_s<-15 ? no