bigintegers's blog

By bigintegers, history, 4 years ago, In English

This is a problem on an algorithms final that I'm studying for.

You are tryng to get from City A to City for the cheapest cost. Your company will pay for exactly one flight between two cities (from a list of flights), but aside from that, you need to drive from the rest of the trip. Given a matrix $$$C[x, y]$$$ that represents the money needed to drive from city $$$x$$$ to city $$$y$$$, and a Boolean matrix $$$F[x, y]$$$, which is TRUE if there's a flight from $$$x$$$ to $$$y$$$ and FALSE otherwise, find an algorithm that finds the minimum amount of money you have to pay to get form $$$A$$$ to $$$B$$$.

This is a problem from a previous final that I am studying with. Apparently the full credit solution was something that runs in $$$\mathcal{O}(V^2)$$$ time, but the only solution that I can think of is to run Dijkstra's $$$n^2$$$ times (bruteforce). Can someone please help me study? We haven't covered anything super advanced (this is an intro algorithms class).

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

| Write comment?
»
4 years ago, # |
Rev. 4   Vote: I like it +4 Vote: I do not like it

If I understood the problem correctly, run Dijkstra from the city where you need to finish, determining the costs of paths to all other cities from it. Do the same from the starting city to all other cities. It is going to take $$$O(V^2)$$$ (two Dijkstras).

Now that you have two arrays, the first one, $$$s[]$$$, denoting the respective costs of paths to all cities from the starting point, and the second one — from the finishing, $$$f[]$$$, just bruteforce all ordered pairs of cities $$$(i, j)$$$, between which flight is available, and take the minimum sum of $$$s[i] + f[j]$$$ — this will be the answer.

»
4 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Dijkstra's gives you the shortest path from one node to all others. Define:

$$$S_i$$$ — the shortest path (driving only) from $$$A$$$ to $$$i$$$

$$$T_i$$$ — the shortest path (driving only) from $$$i$$$ to $$$B$$$

The $$$S_i$$$ values you can compute in $$$O(n^2)$$$ with a single Dijkstra's. The $$$T_i$$$ values you can compute with a single Dijkstra's as well, by inverting the graph and running a Dijkstra's from $$$B$$$.

Now for every edge between a pair of nodes $$$U$$$-$$$V$$$ that has a flight allowed, just consider $$$S_U + T_V$$$ and take the minimum of all.

»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Almost the same problem (uses same idea) if you wish to implement it: https://cses.fi/problemset/task/1195

»
4 years ago, # |
Rev. 2   Vote: I like it +6 Vote: I do not like it

Another alternative to the given solutions is to create extra nodes. Represent each city $$$u$$$ with two nodes $$$u_1$$$ and $$$u_0$$$, a node where you haven't used the flight and another where you have. Then, for each road between any two nodes u and v, two edges $$$u_1 - v_1$$$ and $$$u_0 - v_0$$$ should exists. Planes from $$$u$$$ to $$$v$$$ go instead from $$$u_1$$$ to $$$v_0$$$. To cover the possibility of not using planes, remember to add an edge between $$$B_1$$$ and $$$B_0$$$ of cost $$$0$$$. The answer is given as the minimum distance between $$$A_1$$$ and $$$B_0$$$.

Also, this approach can be easily transformed to deal with cases where you can take $$$2$$$ or more planes.