Let G=(V,E) be a directed graph. Let s in V be a vertex. Let k in V be some vertex such that k≠s. Given a path p, define its cost to be the number of edges in p. However, if a path passes through vertex k, then each edge used after vertex k has been visited counts as 5.

For every v in V, denote by c(s,v) the cost of the cheapest path from s to v. Suggest an efficient algorithm for computing, for every v in V, the value c(s,v).

I also can't use Dijkstra's algorithm.

My initial thought was to use Single-Source Shortest Path algorithm.

Here is my attempt:

Algorithm:

1. Use BFS to calculate all of the paths (unweighted) from s to v, storing the paths in a list.
2. Iterate through each path from the list, and if k is in the path, count the number of nodes after k (assign that to a variable num), and add 4*num to the already calculated sum from step 1.
3. Choose the path with the minimum resulting number, and return it.

I think I can do better than this, becuase in the worst case, we will have |V|/2 paths, so the time complexity can be O(n^2).

I'd like to hear some suggestion to improve the task.

Thanks a lot!

CodePudding user response：

There can only be 2 types of paths - those that go through k and those that don`t:

1. s --> ... --> v
2. s --> ... --> k --> ... --> v

Now to find paths of first kind we can simply do BFS from node s with special condition - we can't ever go anywhere if we happen to reach node k

For other paths we can split them into 2 parts, s --> ... --> k and k --> v, notice that first part is already known by first BFS. Now we can do BFS again, this time from node k.

Now shortest path s --> v for any v is simply just min(type1PathCost[v], type1PathCost[k] type2PathCost[v] * 5)