Shortest Path between 2 fixed nodes, with edge cost update

Revision en1, by RestingRajarshi, 2017-10-08 06:33:53

I have a undirected graph, with 0/1 edge cost. The graph is a complete graph. I have two operations: -- update: flip the edge cost of a particular edge. that is, if it's cost was 0, make it 1, or vice versa. -- query: shortest path between the source and target vertex.

We are given the graph as a adjacency matrix, as well as the source and the target node in the input. The source and the target node remain fixed. Expected memory is o(n^2) (obviously) and time complexity is o(logn) for both update and query.

Thanks for any help in advance.

Tags all-shortest-path, update, complete graph


  Rev. Lang. By When Δ Comment
en1 English RestingRajarshi 2017-10-08 06:33:53 620 Initial revision (published)