Come posso trovare tutte le connessioni in una rete mesh / grafico?

1

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.

    
posta random65537 22.09.2013 - 05:28
fonte

1 risposta

1

Esistono due algoritmi principali che vengono utilizzati per calcolare il percorso più breve; Algoritmo di Dijkstra & Bellman-Ford . Se stai cercando valori ponderati da calcolare, devi consultare code prioritarie . Dovrai anche comprendere il Routing Information Protocol (RIPng per IPV6) per capire esattamente come La tabella di routing è organizzata.

Per esempi di implementazioni dell'algoritmo di Dijkstra puoi vedere l'implementazione qui . Un'implementazione Java dell'algoritmo di Dijkstra con l'accodamento Fast Priority qui .

E, qualcosa che sembra essere una vecchia pagina dedicata a qualcosa di simile ai tuoi requisiti qui

    
risposta data 22.09.2013 - 14:51
fonte

Leggi altre domande sui tag