number of shortest paths between 2 vertex of a graph

Question

Hey, 1) Anyone has an idea to get the number of shortest paths in an undirected unweighted graph? I wanna fill a 2 dimensional matrix which has the number of shortest paths for any i,j vertex, 2) another question is how to get number of shortest paths between two vertex i,j in a way that the path must pass a certain vertex. Thanks in advance.

Answer 1

Dijkstra's algorithm is used to find the shortest paths.

NB First thing Google finds if you tried using it with a shortest path algorithm search...

Answer 2

Dijkstra http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm is your friend. To find the shortest path including a specific node, apply Dijkstra to get the shortest path from A to B and then from B to C. There it is...

To get the number of paths that share the same cost, it should be easy to modify Dijkstra for this, in order to leave something for your homework... :)

Answer 3

dijkstra is for a weighted graph,mine is unweighted. I searched for it in google but found no result for NUMBER of shortest paths,any other help?

Answer 4

i reached somewhere near dynamic programming ,but that solution was too difficult to understand. I want to know if any easier way exists?

Answer 5

of course our friend's question is about undirected so I think even dijkstra isn't needed,you can handle it with bfs,but one thing I dont know is that if you use bfs,how do you want to differentiate previous paths.any comments?

Answer 6

You can use BFS for this situation. Here is an algorithm I've just made up from my memory of some AI courses a couple of years ago. I can't make sure it works flawlessly but hopefully it will give you some hints.

Let X(p, d) denote the node X whose parent is p and the distance from its parent is d.

function findAllShortestPaths(...):

RET = set()
queue = [S(None, 0)]
explored = set()
while queue is not empty:
    Node = queue.dequeue()

    if Node is the one we're searching for:
        if Node is not in RET:
            RET.add(Node)
        else:
            if Node.d <= d of the node in RET:
                RET.add(Node)
        continue

    if Node is not in explored:
        explored.add(Node)
    else:
        if Node.d <= d of the node in explored:
            explored.add(Node)
        else:
            continue

    for Child in Node.childrens:
        if Child is not in explored:
            queue.append(Child(Node, Node.d + 1))

    return RET, explored

Here is an example. Assume you have a 5-point (A, B, C, D, E) graph whose lines are connected as follows; AB, BC, CD, DA, EA, EB, EC, ED. You want to find all shortest paths from A to C.

Let X(parent, distance) ---> Y(...) Z(...) mean X is added to the explored set, Y and Z are X's children and they are added to the queue.

A(None, 0) ---> B(A, 1) E(A, 1) D(A, 1)
B(A, 1)    ---> E(B, 2) C(B, 2)
E(A, 1)    ---> C(E, 2) D(E, 2)
D(A, 1)    ---> C(D, 2)

[E(B, 2) already in the explored list and the distance is 2 > E(A, 1), continue.]

C(B, 2)    ---> Our GOAL, add to RET
C(E, 2)    ---> Our GOAL, C already in RET but distance is equal, add to RET

[D(E, 2) already in the explored list and the distance is 2 > D(A, 1), continue.]

C(D, 2)    ---> Our GOAL, C already in RET but distance is equal, add to RET

Finally, RET contains C(B, 2), C(E, 2), C(D, 2). From here and combining with the explored list, you can trace back to the source node. For example, C(B, 2) B(A, 1) A(None, 0).

There might be some bugs but I think it's not a big deal. For the second question, it's not too far away once we have figured out the first one. Hope it help!

Answer 7

Hi

Let admat be the adjacency matrix for your graph. Then

admat gives the length 1 paths between vertices;

admat^2 gives the length 2 paths between vertices;

admat^3 gives the length 3 paths between vertices;

spot the pattern yet ?

Regards

Mark