Assignment No: 10 Shortest Paths in Graphs Solution

Foobarland has n cities numbered 0, 1, 2, . . . , n − 1. The official airline for Foobarland is Air Ifoobria (AI). For any pair (i, j) of cities with i = j, there are three possibilities: (i) there are flights from i to j operated by AI, (ii) there are flights from i to j operated by private (non-AI) airlines, and (ii) there are no flights from i to j. Here, a flight means a direct (that is, non-stop) flight. For every city-to-city flight leg, the operating airline declares a ticket price. The existence of flights and the prices are not symmetric. That is, there may be a flight from City i to City j but not from City j to City i. Even when two cities are two-way connected, the airline and/or price for one direction may be different from those in the other direction.

You naturally model the flight information using a directed graph G = (V, E ). The vertices of G are the cities of Foobarland. If there is a flight from City i to City j, then there is a directed edge from Vertex i to Vertex j. Each edge carries two items: (i) whether the operator is AI or non-AI, and (ii) the price of the ticket.

Rules in Foobarland prohibit government employees from traveling by non-AI flights for official works. Mr. Sarkar from the Aviation Ministry is given the task of preparing charts of minimum city-to-city flight prices with multiple legs allowed. He plans to build three charts.

    1. The first chart is based only on AI flights.

    2. It is possible that some pairs of cities are not at all connected by AI flights. A second chart is needed where only one non-AI leg is allowed in each route not served by AI.

    3. In case a pair of cities is not connected by AI flights, any schedule that can connect the pair with an arbitrary number of non-AI legs is to be stored in the third chart.

The following figure demonstrates the situation. AI flights are shown by red edges, and non-AI flights by blue edges. The prices shown in the figure are scaled-down versions of the example given in the Sample I/O section. On the left, you have the entire flight schedule for both AI and non-AI airlines. In the center, only the AI flights are shown. There is no AI-operated path from City 4 to City 2. But if you allow one non-AI leg (edge), you have two paths 4, 0, 3, 2 and 4, 0, 5, 3, 2 of costs 21 + 92 + 91 = 204 and 21 + 95 + 29 + 91 = 236 (see the right side of the figure). If you allow multiple non-AI legs, there is another path 4, 0, 5, 2 from City 4 to City 2 having cost 21 + 95 + 48 = 164. As another example, City 1 cannot be connected to City 0 unless multiple non-AI legs are allowed.



0
21


0


0
21












1

91
2
1
91
2
1

91
2











92


48
92


92














3

76
4
3

4
3


4

95



95





29


69
29

69
29
95

69












5



5


5














Part 1: The graph data type and its construction

A flight-schedule graph consists of three items: (i) the number n of cities (an integer), (ii) an n × n array of operator airlines (use a character for each entry), and (iii) an n × n array of integers storing the ticket prices. This is similar to an adjacency-matrix representation.

—  Page 1 of 3  —
The (i, j)-th entry of the operator array stores a if there is an AI-operated flight from City i to City j, or n if there is a non-AI flight from City i to City j, or − if there is no flight from City i to City j, or s (stay put) if i = j. If i = j and there is no flight from City i to City j, store +∞ as the ticket price. For i = j, store 0 as the ticket price.

Write a function readgraph that constructs G from user inputs, and returns it. The user first enters n (the number of cities). The user then supplies quadruples (i, j, ci j , ai j ), where i is the source city, j is the destination city, ci j is the ticket price for the City i → City j flight, and ai j is the operator airline of that flight (a if AI, n if non-AI). The user input ends when −1 is supplied as i.

Part 2: Build the AI subgraph

Write a function getAIgraph(G) that produces the subgraph H of G storing only the AI flights (all vertices but only the red edges, as in the center of the figure on the previous page).

Part 3: APSP in the AI subgraph

Implement a function APSP to implement the Floyd–Warshall all-pairs-shortest-path algorithm. When you call this function with the AI subgraph H as input, you get the first chart C1 of Mr. Sarkar.

Part 4: APSP with one non-AI leg allowed

The second chart C2 of Mr. Sarkar keeps all the entries of C1, that are less than ∞ (indicating AI connectivity). Only when C1(i, j) = ∞, you need to figure out whether by allowing a single non-AI leg, you can connect City i to City j. One possibility is to add a single non-AI edge to H , and run APSP on this graph. This is to be done one by one for all non-AI edges. Since there are O(n2) non-AI edges, and the running time of Floyd–Warshall is O(n3), you end up with an O(n5) running time.

The problem can however be solved in O(n4) time. If C1(i, j) = ∞, choose a non-AI flight (k, l). You may have i = k or l = j or both. Check whether C1(i, k) + the cost of the k → l flight + C1(l, j) is < ∞. If so, an allowed i → j route is discovered. Minimize over all non-AI flights (k, l). Write a function APSPone(G,C1) to implement this idea.

Part 5: APSP with any number of non-AI legs allowed

In the third chart C3 of Mr. Sarkar, we again have C3(i, j) = C1(i, j) if C1(i, j) < ∞ (if AI provides an i → j service, you have to take it, even if using non-AI legs can reduce the price). However, there is now no restriction on the number of non-AI legs in each minimum-price i → j path (provided that C1(i, j) = ∞). Write a function APSPany(G,C1) to build the third chart C3. The design of the algorithm is left to you. Your algorithm should run in O(n3) time.

The MAIN() function

    • Call readgraph to get the flight-schedule graph G.

    • Call getAIgraph to get the AI flight-schedule subgraph H .
    • Call APSP on H to get C1. Print C1.

    • Call APSPone to get C2. Print C2.

    • Call APSPany to get C3. Print C3.

Note: The charts C1,C2,C3 store only the cheapest flight prices. In this assignment, you do not have to prepare the cheapest allowed routes.


Submit a single C/C++ source file. Do not use global/static variables.







—  Page 2 of 3  —
Sample I/O

The example given below corresponds to the figure on the first page. Better and larger samples will be provided in a separate file. A - in the charts indicates unavailability of flight routes.

6




0
3
9199
a

0
5
9484
a

1
4
7624
n

3
2
9055
a

4
0
2127
n

5
2
4830
n

5
3
2901
a

5
4
6877
a

-1




+++
Original
graph


0
->
3 (9199, a)
5 (9484, a)

    1 ->   4 (7624, n)

    2 ->

    3 ->   2 (9055, a)

    4 ->   0 (2127, n)

5    ->    2 (4830, n)    3 (2901, a)    4 (6877, a)

+++ AI subgraph

0    ->    3 (9199, a)    5 (9484, a)

    1 ->

    2 ->

    3 ->   2 (9055, a)

    4 ->

5    ->    3 (2901, a)    4 (6877, a)

+++ Cheapest AI prices






0
1
2
3
4
5
0
->
0
- 18254
9199
16361
9484
1
->
-
0
-
-
-
-
2
->
-
-
0
-
-
-
3
->
-
-
9055
0
-
-
4
->
-
-
-
-
0
-
5
->
-
- 11956
2901
6877
0
+++ Cheapest prices with at most one non-AI leg


0
1
2
3
4
5
0
->
0
- 18254
9199
16361
9484
1
->
-
0
-
-
7624
-
2
->
-
-
0
-
-
-
3
->
-
-
9055
0
-
-
4
->
2127
- 20381
11326
0
11611
5
->
9004
- 11956
2901
6877
0
+++ Cheapest prices with any
number of non-AI legs


0
1
2
3
4
5
0
->
0
- 18254
9199
16361
9484
1
->
9751
0
24065
18950
7624
19235
2
->
-
-
0
-
-
-
3
->
-
-
9055
0
-
-
4
->
2127
- 16441
11326
0
11611
5
->
9004
- 11956
2901
6877
0
















—  Page 3 of 3  —