LabASD - Algoritmo di Dijkstra

Moreno Marzolla moreno.marzolla@unibo.it

Ultimo aggiornamento: 2021-05-06

Implementare l'algoritmo di Dijkstra per il calcolo del cammini minimi da singola sorgente in un grafo orientato pesato con pesi non negativi. L'algoritmo di Dijkstra richiede un nodo di partenza \(s\), e opera sfruttando una coda di priorità (già implementato nei programmi minheap.c e minheap.h).

Edsger W. Dijkstra By Hamilton Richards - manuscripts of Edsger W. Dijkstra, University Texas at Austin, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=4204157
Edsger W. Dijkstra By Hamilton Richards - manuscripts of Edsger W. Dijkstra, University Texas at Austin, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=4204157

Per inizializzare le distanze a \(+\infty\) si può usare il valore HUGE_VAL definito in <math.h> che rappresenta l'infinito positivo. Questo simbolo è definito nello standard C90, per cui dovrebbe essere presente in tutti i compilatori compatibili.

Il programma legge il grafo di input da standard input, e stampa l'elenco degli archi che fanno parte dell'albero dei cammini minimi su standard output. Il formato dell'input è quello utilizzato dall'interfaccia grafo.

Per sperimentare la propria implementazione con grafi più grandi, si possono usare i file di input seguenti che rappresentano porzioni della rete stradale di alcuni stati americani e della città di Roma:

Dataset Nodi (\(n\)) Archi (\(m\))
Nevada 261155 618175
Maine 194505 425708
Vermont 97975 212979
Delaware 49109 119744
Roma 3353 8859

I file sono stati ottenuti dai dati presenti in questa pagina. Curiosamente, i grafi non sono sempre (fortemente) connessi, quindi non tutti i nodi sono raggiungibili dagli altri nodi (!!).

Per compilare:

    gcc -std=c90 -Wall -Wpedantic minheap.c graph.c dijkstra.c -o dijkstra

Per stampare le distanze e i cammini minimi dal nodo 0:

    ./dijkstra graph10.in 0

Per stampare la distanza e il cammino minimo dal nodo 3 al nodo 4:

    ./dijkstra graph10.in 3 4

dove al posto di 0 si può indicare l'indice di qualunque altro nodo da usare come sorgente.

File