Shortest Path between 2 fixed nodes, with edge cost update

Правка en1, от 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.

Теги all-shortest-path, update, complete graph

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский RestingRajarshi 2017-10-08 06:33:53 620 Initial revision (published)