number of shortest paths between 2 vertex of a graph

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 ho开发者_运维知识库w 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.

---

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 ?

---

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... :)

---

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!

---

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...

---

Using BFS we can minimize the complexity.

Use BFS and and we have to keep an extra counter let Sum(w) in each layer.

let s is the starting vertex and we need to find the no of shortest path to v.

then let w be a node in L(j-1) and v is in L(j).

then S(v)= summation{S(w)} + 1;

and S(v) denotes the no of shortest path between s and v.