Skip to content
Problemi, algoritmi e coding

Problemi, algoritmi e coding

Le magie dell'informatica

  • Home
  • Capitoli
    • Uno
    • Due
    • Tre
    • Quattro
    • Cinque
  • Errata corrige
  • Oltre il libro
    • Uno
      • Il metodo algoritmico
      • Colora la mappa
      • Colorazione di una mappa: il codice
      • Ordinamento per selezione: il codice
      • Indovina il numero
      • L’algoritmo T3: il codice
      • Ordinamento per fusione: il codice
      • Ricerca esaustiva: il codice
    • Due
      • Le domande a Google
      • Shmoogle
    • Quattro
      • Il metodo dei fattori nascosti: visualizzazione
    • Cinque
      • La macchina di Turing
      • Il gioco dell’imitazione
      • L’algoritmo del percettrone: il codice
      • Lost in translation
      • A proposito di traduttori
    • Video
      • Domande e risposte
      • Errare coding est
  • Il metodo PAC
    • Il rompicapo di Guarini
    • Come funziona il time-lapse
    • Fellini e la crittografia
    • Il problema delle donazioni di reni
  • Lucidi
    • Due
    • Tre
    • Quattro
    • Cinque
  • Parlano di noi
  • Chi siamo
  • Toggle search form

Tre

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
Esegui e sperimenta

Copyright © 2023 Problemi, algoritmi e coding.

Powered by PressBook WordPress theme