Cammini minimi¶

3.1 Problemi del percorso più breve

Ottimità dei sottopercorsi

Apri
3.2 Condizioni e potenziali di ottimalità

Apri
3.3 La formulazione della programmazione lineare

Il modello a fonte unica

Apri
3.4 Percorsi più brevi nei grafici aciclici

Apri
3.5 L'algoritmo Bellman–Ford

Apri
3.6 Algoritmo di Dijkstra

Algoritmo di Dijkstra sul grafo di riferimento · Lunghezze negative

Apri

Prerequisiti

Da Capitolo 1 «Grafi»: cammini orientati, percorsi e cicli, la matrice di incidenza nodo-arco, gli alberi e il grafo di riferimento.
Dal modulo Programmazione lineare, Capitolo 9 «Teoria della dualità»: il duale di un modello LP e il teorema della dualità debole.

Obiettivi

Alla fine di questo capitolo sarai in grado di:

indica i problemi \(s\)–\(t\) e i problemi del percorso più breve a sorgente singola e riconosce quando si verifica un ciclo negativo loro mal posati;
utilizza l'ottimalità dei sottopercorsi, le equazioni di Bellman e l'albero dei percorsi più brevi;
scrivi il modello LP di un percorso minimo come flusso unitario, scrivi il suo duale con i potenziali \(\pi_i\) e usa potenziali ammissibili come certificato di ottimalità;
esegue l'algoritmo per grafi aciclici, l'algoritmo Bellman–Ford (con il rilevamento di un ciclo negativo) e L'algoritmo di Dijkstra dimostra la loro correttezza e fornisce il loro tempo di esecuzione.

Avanti: 3.1 Problemi del percorso più breve

Esercizi su questo capitolo: Cammini minimi