Dato un grafo diretto e pesato in cui i pesi degli archi possono essere anche negativi e fissato un suo nodo , vogliamo determinare il costo minimo dei cammini che conducono da a tutti gli altri nodi del grafo Se non esiste un cammino, il costo sarà considerato infinito.
ciclo negativo
Un ciclo negativo è un ciclo diretto in un grafo la cui somma dei pesi degli archi è negativa.
se in un cammino tra i nodi e è presente un nodo che appartiene ad un ciclo negativo, allora non esiste un cammino di costo minimo tra e .
Infatti, ripassando più volte per il ciclo, si abbasserebbe arbitrariamente il costo del cammino.
proprietà
Se il grafo non contiene cicli negativi, allora per ogni nodo raggiungibile dalla sorgente esiste un cammino di costo minimo che attraversa al più archi.
Per trovare cicli negativi: si calcola una riga in più (riga ) e, se la -esima e la -esima riga sono diverse, c’è un ciclo negativo.