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 ?
shortest paths network
Moderator: Board moderators
-
maxdiver
- Learning poster
- Posts: 51
- Joined: Tue Sep 04, 2007 2:12 pm
- Location: Russia, Saratov
- Contact:
Re: shortest paths network
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].
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].
Re: shortest paths network
Thank's for ideas