problema algoritmo programmazione dinamica

[eeeee]

buonasera a tutti sto preparando l'esame di algoritmi e strutture dati e spulciando nei vari esami precedenti ho trovato questo problema:
"Si consideri la rete ferroviaria di trasporto italiana. Assumendo di conoscere il tempo medio di percorrenza di ciascuna tratta,scrivere un algoritmo che permetta di individuare il percorso più veloce fra una stazione di partenza e una stazione di arrivo"

Penso che il problema si risolva con la programmazione dinamica(argomento che la mia prof non ha approfondito ).
Ora leggendo qua e la ed avendo una vaga idea dei problemi di programmazione dinamica, una possibile risoluzione può essere questa?

Divido il mio problema in tanti sotto-problemi più semplici:

T=tempo medio di percorrenza
p=percorso più veloce
sp =tempo da stazione di partenza
sa =tempo a stazione di arrivo
T(sp,sa)= 0 -->se sp=sa cioè non mi muovo
T(sp,sa)= min(sp+sa) -->sp<sa

può essere giusta come inizio di una possibile risoluzione al problema?come implemento tutto ciò con uno pseudocodice?
potrei usare anche un implementazione con l'algoritmo Dijkstra secondo voi?:cry:

[apatriarca]

Direi che Dijkstra è perfetto in questo caso.

[eeeee]

ok quindi dovrei costruirmi un grafico ipotetico con i vertici che rappresentano le stazioni del treno giusto?

[apatriarca]

Certo, quello dei trasporti è in pratica il problema per cui l'algoritmo è stato inventato..

[vict85]

ok quindi dovrei costruirmi un grafico ipotetico con i vertici che rappresentano le stazioni del treno giusto?

Si, è probabilmente il modo più sensato per farlo. Puoi anche lavorare sul grafo duale, ma non penso che in questo casa abbia senso (i percorsi sono sempre da una stazione ad una stazione).

Riguardo ai tuoi "sotto-problemi": i tempi di arrivo sono irrilevanti (non influenzano il tempo di percorrenza). Quello che ti interessa è solo il tempo "totale" di percorrenza di un percorso tra le due stazioni (visto come somma dei tempi medi).

Se vuoi, puoi considerare un dijkstra bidirezionale. Esistono algoritmi che convergono più in fretta, ma generalmente richiedono o qualche pre-computazione oppure di rinunciare alla soluzione ottimale. È probabilmente possibile trovare una qualche euristica per \(A^*\) che sia ammissibile e monotona sul tuo particolare grafo, ma è probabilmente uno sforzo eccessivo per un esame.