shortest paths network

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
nicoletsg
New poster
Posts: 15
Joined: Sat Dec 20, 2008 8:10 pm

shortest paths network

Post by nicoletsg »

In a network i want to find the number of alternate shortes paths from a start node to all other nodes. Normally Dijkstra can be used.
But because there are no weights BFS should also working.
I can modify BFS algorithm so that pred (n) doesn't only store one predecessor
but a list of possible predecessors. So i have now the PATHs
But is there any way to calculate the Number of shortest paths from a start node to rest of nodes ?

maxdiver
Learning poster
Posts: 51
Joined: Tue Sep 04, 2007 2:12 pm
Location: Russia, Saratov
Contact:

Re: shortest paths network

Post by maxdiver »

You don't even need in pred[], only distances dist[] from vertex s to the others.
After that, calculate for each vertex dynamics: d[v] is the number of shortest paths to v.
Set d[s] = 1.
For each other vertex d[v] = SUM d[p] over all p such that dist[p] + g[p][v] == dist[v].

nicoletsg
New poster
Posts: 15
Joined: Sat Dec 20, 2008 8:10 pm

Re: shortest paths network

Post by nicoletsg »

Thank's for ideas

Post Reply

Return to “Algorithms”