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