CODEWITHSUNDEEP
graph
chanakya sunkarapally
chanakya sunkarapally

Reputation: 69

How to efficiently find path between all pairs of nodes in a graph?

Given is a graph with n vertices and n-1 edges that join all the vertices. I am using adjacency lists to store edges. I want to find path between different pairs of nodes (which are taken as input) in the most efficient way? How to go about it?

EDIT: I also want to store the previously found paths somewhere, so that if path between two nodes has already been found, directly or indirectly, I don't have to find it again.

Upvotes: 0

Views: 504

Answers (2)

Alekos
Alekos

Reputation: 378

If you have on each node the father of himself you can go up to the root, step by step make a path to the root and then compare if you find the same node in the other path (the one from the other node to the root).

root ---a---b---c---d---e
        |
        f---g---h---i
            |
            j---k---l

In this example you want to go from c to i.

Path to root for i -> {i, h, g, f, a, root}

Path to root for c -> {c, b} break //same node found in i's list ("a")

Create a new list with the c's list and the reverse i's list from 0 to (index of "a")

Path from c to i -> {c, b, a, f, g, h, i}

        a---b---c
        |
        f---g---h---i

Upvotes: 2

Matt Timmermans
Matt Timmermans

Reputation: 59174

Pick a node to be the root and mark each node with its depth.

Then, given pointers to two nodes, move the deeper one up until they are at the same depth, and then move them both up in step until they meet.

Upvotes: 0

Related Questions