OJ Board

hi all,
In this volume there are some problems involving computing
every shortest path between a given pair of nodes.
(like Problem 10354 and Problem 10331)
In most cases, we often need only one shortest path between
a given pair of nodes and thus we can use an array to record the parent
of a node in the Shortest Spanning Tree(SPT).
But I don't know how to record every shortest path between a source and
a sink. That is, how can we record all SPT and contruct all shortest paths if necessary?
Can someone explain this? Great thanks!

I don't know if it's efficient enough, but for 10354, I did Floyd-Warshall to compute all-pairs shortest-path ... Since the source and sink are given, ... we can see the shortest-path cost ...

I then did a loop for each vertex to be a 'medium' from source to sink ... If (cost[source][medium]) + (cost[medium][sink]) == shortest-path cost ... that means medium must be considered as a vertex that can make a shortest-path happen ...

And after that ... I guess it's simple enough to figure out the rest ...

-turuthok-

Thanks for your reply.
I think this is a simple and clear solution to the problem 10354.
But I still have no idea about how to record all SPT.
Can we use Floyd-Warshall algorithm for problem 10331?
How do we update and restore all possible paths?

turuthok wrote:I don't know if it's efficient enough, but for 10354, I did Floyd-Warshall to compute all-pairs shortest-path ... Since the source and sink are given, ... we can see the shortest-path cost ...

I then did a loop for each vertex to be a 'medium' from source to sink ... If (cost[source][medium]) + (cost[medium][sink]) == shortest-path cost ... that means medium must be considered as a vertex that can make a shortest-path happen ...

And after that ... I guess it's simple enough to figure out the rest ...

-turuthok-

Hello, ... I kinda believe that 10331 can be solved using similar approach, however, I haven't been able to get AC ...

I still run Floyd-Warshall to get all-pairs shortest-path.

Then I loop thru each road that we get from input to see if it can be used as 'medium'. We know each road connect s to t with cost c ... then I check if for all i, j elements of V ...

if d[s] + c + d[t][j] == minCost[j] ... then you can actually use road s-t to get from i -> j ...

But again, I haven't got accepted yet ... Please don't quote me completely.

-turuthok-

Hi google,
you can save an array of parents for each node instead of a single parent and use Djikstra for each source node.

Google wrote:Thanks for your reply.
I think this is a simple and clear solution to the problem 10354.
But I still have no idea about how to record all SPT.
Can we use Floyd-Warshall algorithm for problem 10331?
How do we update and restore all possible paths?