algoritmo per calcolare distanze

[strategie79]

ciao a tutti

volevo sapere se esistono algoritmi scritti in php,
e se era possibile reperire il codice,
per il calcolo di percorsi tra diverse città.
devo fare in modo che venga trovato il percorso più breve
immagino sia una sorta di visita in ampiezza..
grazie!

[garlick]

Cerca su google informazioni sugli algoritmi di Dijkstra e Bellman-Ford. In particolare il primo è più efficiente del secondo ma funziona solo in assenza di cicli negativi, quindi vedi se può fare al caso tuo. Implementare l'algoritmo in Php non dovrebbe essere troppo complicato.

Dijkstra su Wikipedia
altri algoritmi

[andr3a]

visto che Dijkstra vuole sapere a priori il costo degli spostamenti, tanto vale usare l' A Star (A*) e mettere il grafo in griglia per costi.

L'A Star è molto più trattato, io ne ho fatto uno in JavaScript e ActionScript ma durante i miei studi ne avevo trovati anche già pronti in PHP.

Tutto stà vedere quali siano le tue reali necessità

[strategie79]

grazie per le risposte ragazzi

cmq il mio problema è proprio l'inverso:
conosco già l'algoritmo dijkstra per averlo implementato in un altro linguaggio (C)
quello che non conosco è proprio l'implementazione in php
per quello andavo in cerca di codice già esistente.. mi sa che non si trovi però, vero?

riguardo l'A* non sapevo nulla, sto dando un'occhiata ma sembra un pò complicato..
ma magari sono io il problema

ciao a tutti

[strategie79]

preciso quello che volevo fare:
devo raggiungere una città B da una città A
avrò un database con le coppie di adiacenti
con i campi per le distanze e i tempi di percorrenza ecc
voglio scrivere l'algoritmo che mi calcoli
la strada breve o la strada con minor tempo di percorrenza
avevo pensato anche di sfruttare le coordinate lat/long
per dirigermi verso nord/sud est/ovest
ma sembra un pò complicato!
insomma, una specie di viamichelin.. non so proprio come districarmi