Supponiamo che abbia una trama di relazioni, come
- Amici che si fidano di alcuni amici e non di altri
- Un router IPv6 che deve individuare i peer su Internet
- Un Web Of Trust PGP che ha bisogno di due persone per individuare il reciproco livello di attendibilità
Sono interessato a determinare non solo il percorso più breve, ma il costo di ciascuno (un peso arbitrario da aggiungere), i nodi di ciascun percorso e altre informazioni tipicamente utilizzate in questo scopo generale.
Quali approcci ci sono per soddisfare questo bisogno? Idealmente questo sarà qualcosa che posso eseguire localmente su un telefono o un computer e cercare un grafico di grandi dimensioni con velocità O (N) o superiore.