Come ci arrivo e quanto tempo impiego?
Di cosa si parla
I satelliti e l’algoritmo di Dijkstra alla base di un fidato compagno di viaggio: il GPS e il navigatore.
Incipit
L’uomo ha sempre amato viaggiare per mare e per terra, attraverso fiumi e montagne, a piedi, a cavallo, in barca, con carri tirati dai buoi, in ogni modo possibile.
Avendo a disposizione una carta stradale, come possiamo trovare il percorso migliore per andare da un posto a un altro?
Rappresentando la carta stradale come un grafo, a ogni passo ci allontaniamo il meno possibile dal punto di partenza e aggiorniamo le informazioni a nostra disposizione e ancora da elaborare. Questo, in breve, è l’algoritmo di Dijkstra.
function dijkst(g,n,s,d,f)
for i = 1:n
x = trovamin(d,f,n)
f[x] = true
for y = 1:n
nd = d[x]+g[x,y]
if g[x,y]>0&& d[y]>nd
d[y] = nd
end
end
end
return d
end