Let us assume a connected graph with large number of nodes without weight in the edge. Also assume that entire information is not available (i.e. adjacency matrix is not available). One node is having information of its neighbor only. Now I want to find a path to destination. How do I find one path which is shortest among various possible path.
I would assume that breadth-first search should be able to find it. Another option is - I think - to solve the shortest path algorithm by setting an artificial weight 1 (one) on each edge - the shortest path to your destination must then be one with the least number of links used!
Hi Monjul, if you are also interested in approximating the shortest paths, here is a paper for this task:Fast Shortest Path Distance Estimation in Large Networks (attached link). In addition, if every node holds information about its neighbors, then this is basically your adjacency list and you can use it to compute the shortest paths. As Michael mentioned, BFS is also a valid option.
http://cs-people.bu.edu/mp/images/pap091.pdf
- Badges
- Science topic
- Similar topics
- Mathematical Sciences
- Graphs