trains's blog

Shortest path in time-dependent graph
By trains, 10 years ago, In English

Hello!

There is graph with time-dependent edges(their weight changes in time).

For example, at moment 0 its the adjacency matrix looks like:

inf 5 3 inf
5 inf 3 10
3 3 inf inf
inf 10 inf inf

but at moment 6 it changes to

inf 5 3 inf
5 inf 3 1
3 3 inf inf
inf 1 inf inf

So, path 1->2->4 will take 5+10; path 1->3->2->4 will take 3+3+10 in time-independent but 3+3+1 in time-dependent graph. I wonder, if anyone know such problem in problem-set archive?

  • Vote: I like it
  • +4
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think Problem #6485 on https://icpcarchive.ecs.baylor.edu (I prefer not to share the link, the problem description link leads to a PDF file. You can look it up here) would fit your needs.

→ Reply