1

Suppose I have a mesh of relationships, such as

  • Friends who trust some friends and not others
  • A IPv6 router that needs to locate peers across the Internet
  • A PGP Web Of Trust that needs two people to locate each other's trust level

I'm interested in determining not only the shortest path, but the cost of each (an arbitrary weight by be added), the nodes of each path, and other information typically used in this general purpose need.

What approaches are there to accommodate this need? Ideally this will be something that I can run locally on a phone or computer and search a large graph in O(N) speed or better.

makerofthings7
  • 6,038
  • 4
  • 39
  • 77

1 Answers1

1

There are 2 major algorithms that are used to compute shortest path; Dijkstra's Algorithm & Bellman-Ford. If you're looking for weighted values to be calculated as well you need to look into priority queues. You'll also need to understand the Routing Information Protocol (RIPng for IPV6) to understand just how the Routing Table is organized.

For examples of implementations of Dijkstra's Algorithm you can see the implementation here. A Java implementation of Dijkstra's Algorithm with Fast Priority Queueing here.

And, something that looks to be a rather old page dedicated to something close to your requirements here

Josh Tollefson
  • 61
  • 3