Shortest path between two vertex in a complete graph [duplicate]

Question

This question already has answers here:

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

Closed 9 years ago.

I have a complete graph with N vertices and I need to find the shortest path from a given source to a given destination. All edges have initial cost A, then for K edges the cost will change to B. What is the best way to find the minimal cost between vertex 1 and vertex N [The algorithm finds the lowest cost (i.e. the shortest path) between vertex 1 and vertex N]? The input is N K A B and K edges (the edges with cost B).

where:

2 <= N <= 500000
0 <= K <= 500000
1 <= A, B <= 500000

I've tried with Dijkstra but take to much time ~ 2min, and i need something like 2sec.

Answer 1

1. If the cost of the edge between 1 and N is A.

   1) if A<B, then the lowest cost will be A.

   2) if A>B, then use BFS to find the fewest hops from 1 to N through only the edges with cost B. Assume that there are at lestL edges between 1 and N, then return min(LB,A). It is typical BFS and the cost is O(N+K).

2. If the edge between 1 and N is B.

   1) if 'A>B', then the answer is B.

   2) Find the fewest hops from 1 to N only using the edge with cost A. Let S[h] be the set of vertices can be reached by h hops and S' be the set have not reached yet, then it can be solved as follows.

   min_dis() { S[0] = {1}; int h = 0; S'={2,...,N}; while (S[h] is not empty) { S[h+1] = {}; for_each (v1 in S'){ for (v2 in S[h]) { if (cost[v1][v2] == A) { S[h+1].insert(1); S'.remove(v1); if (v1 == N) return min((h+1)*A, B); break; } } } h++; } return B; }

   We can proof that this algorithm is also O(N+K), since each time we testconst[v1][v2]==A is true , the size of S' will be decreased by 1 and there are at most K time when this test is false because there are at most K edge with cost B. So it guarantees to be finished with O(N+K)

In total, the algorithm is O(N+K), which will guarantee the 2sec time limit.