Complete graph with only two possible costs. What's the shortest path's cost from 0 to N - 1

9
votes

You are given a complete undirected graph with N vertices. All but K edges have a cost of A. Those K edges have a cost of B and you know them (as a list of pairs). What's the minimum cost from node 0 to node N - 1.

2 <= N <= 500k
0 <= K <= 500k
1 <= A, B <= 500k

The problem is, obviously, when those K edges cost more than the other ones and node 0 and node N - 1 are connected by a K-edge.

Dijkstra doesn't work. I've even tried something very similar with a BFS.

Step1: Let G(0) be the set of "good" adjacent nodes with node 0.
Step2: For each node in G(0):
              compute G(node)
              if G(node) contains N - 1
                  return step

              else
                  add node to some queue
       repeat step2 and increment step

The problem is that this uses up a lot of time due to the fact that for every node you have to make a loop from 0 to N - 1 in order to find the "good" adjacent nodes.

Does anyone have any better ideas? Thank you.

Edit: Here is a link from the ACM contest: http://acm.ro/prob/probleme/B.pdf

4
algorithmgraphdijkstrashortest-pathbreadth-first-search
Also a problem when A > B and the edge from 0 to N-1 costs A. You may be able to form a k*B < A path in this case. – Gassa
Yeah, but that's not really a problem, because you only have 500K B-edges. And you can "afford" doing a BFS on those B-edges graph. The problem is when you have to explore the complementary graph (because those are the cheap edges). – fanton
What do you mean, Dijkstra doesn't work? Is it too expensive, or is there something about the problem that causes it to fail? – user2357112 supports Monica
I mean that Dijktra is too time expensive for this problem. O(E * logV) means roughly 10^15 operations in worst case scenario. Waay too much. – fanton
@FlaviusAnton Is this problem online somewhere? I'd like to solve it – Niklas B.

4 Answers

3
votes

This is laborous case work:

  1. A < B and 0 and N-1 are joined by A -> trivial.
  2. B < A and 0 and N-1 are joined by B -> trivial.
  3. B < A and 0 and N-1 are joined by A -> Do BFS on graph with only K edges.

  4. A < B and 0 and N-1 are joined by B -> You can check in O(N) time is there is a path with length 2*A (try every vertex in middle).

    To check other path lengths following algorithm should do the trick: Let X(d) be set of nodes reachable by using d shorter edges from 0. You can find X(d) using following algorithm: Take each vertex v with unknown distance and iterativelly check edges between v and vertices from X(d-1). If you found short edge, then v is in X(d) otherwise you stepped on long edge. Since there are at most K long edges you can step on them at most K times. So you should find distance of each vertex in at most O(N + K) time.

2
votes

I propose a solution to a somewhat more general problem where you might have more than two types of edges and the edge weights are not bounded. For your scenario the idea is probably a bit overkill, but the implementation is quite simple, so it might be a good way to go about the problem.

You can use a segment tree to make Dijkstra more efficient. You will need the operations

  • set upper bound in a range as in, given U, L, R; for all x[i] with L <= i <= R, set x[i] = min(x[i], u)
  • find a global minimum

The upper bounds can be pushed down the tree lazily, so both can be implemented in O(log n)

When relaxing outgoing edges, look for the edges with cost B, sort them and update the ranges in between all at once.

The runtime should be O(n log n + m log m) if you sort all the edges upfront (by outgoing vertex).

EDIT: Got accepted with this approach. The good thing about it is that it avoids any kind of special casing. It's still ~80 lines of code.

1
votes

In the case when A < B, I would go with kind of a BFS, where you would check where you can't reach instead of where you can. Here's the pseudocode:

G(k) is the set of nodes reachable by k cheap edges and no less. We start with G(0) = {v0}

while G(k) isn't empty and G(k) doesn't contain vN-1 and k*A < B
  A = array[N] of zeroes
  for every node n in G(k)
    for every expensive edge (n,m)
      A[m]++
  # now we have that A[m] == |G(k)| iff m can't be reached by a cheap edge from any of G(k)
  set G(k+1) to {m; A[m] < |G(k)|} except {n; n is in G(0),...G(k)}
  k++

This way you avoid iterating through the (many) cheap edges and only iterate through the relatively few expensive edges.

0
votes

As you have correctly noted, the problem comes when A > B and edge from 0 to n-1 has a cost of A.

In this case you can simply delete all edges in the graph that have a cost of A. This is because an optimal route shall only have edges with cost B.

Then you can perform a simple BFS since the costs of all edges are the same. It will give you optimal performance as pointed out by this link: Finding shortest path for equal weighted graph

Moreover, you can stop your BFS when the total cost exceeds A.