Question

For your second co-op you are developing the next state-of-the- art flight search engine. You have the list of all n daily flights in the world.

1. For each flight you have starting city, destination city, and price (a positive number).

Give an efficient algorithm to compute the cheapest trip from start city to end city t . You can use any number of flights in your trip.

2. Same as part 1, but if multiple trips with the same cost exist, the algorithm should find the trip with the least number of flights. You can assume that the cost of each flight is an integer >0.

3. Each flight is operated by exactly one of two airline companies

A and B. One of your customers is on an impartial federal trip, and cannot favor any airline over the other. Give an efficient algorithm to compute the cheapest trip from start city s to end city t such that no two consecutive flights are from the same airline. You can use any number of flights in the trip.

Answer 1

We have starting city, destination city and price for travel between starting city and the destination city.

1. We have to find out the cheapest travel path from starting city to destination city.

     Let us take a directed graph.
     Cities will be represented by vertices and price will be the weight of edge between the vertices.

    So, this problem reduces to Dijkastra's shortest path algorithm.
    Dijkastra's algorithm finds shortest path cost from source to all other vertices. We will stop Dijkastra's algorithm when we have found out the cheapest path from source to destination city.

Algorithm:

1. Create a treeSet : Initially empty. It will contain all those vertices whose minimum cost from the source has been calculated.
2. Initially, all cost of the edges will be set to infinite and the cost of source vertex will be 0 so that it is selected as the source vertex.
3. Now, a loop till treeSet does not include the destination vertex.
             Steps in loop : i. Select the vertex x which has minimum cost from source. If it is not already added to the treeSet, add it to the treeSet.
ii. Now, update cost of all vertices which are connected to this x. Now, for all           adjacent vertices, update their cost if it is less than the sum of cost from source vertex and the cost of edge between x and the adjacent vertex.

2. In this part, we will have to keep the count of total number of vertices traversed to reach the destination.

     Dijkastra's algorithm finds shortest path cost from source to all other vertices. This time we will not stop when we reach destination.

Algorithm:

1. Create a treeSet : Initially empty. It will contain all those vertices whose minimum cost from the source has been calculated.
2. Initially, all cost of the edges will be set to infinite and the cost of source vertex will be 0 so that it is selected as the source vertex. Also, all vertex_traversed_count will be set to infinite except the source vertex.
3. Now, a loop till treeSet has all vertices.
             Steps in loop : i. Select the vertex x which has minimum cost from source. If it is not already added to the treeSet, add it to the treeSet.
ii. Now, update cost of all vertices which are connected to this x. Now, for all    adjacent vertices, update their cost if it is less than the sum of cost from source    vertex and the cost of edge between x and the adjacent vertex. Also, for all vertices    update the vertex_traversed_count i.e., how many vertices did one needs to
                                       traverse for reaching this vertex from the source vertex.
Finally, from among multiple shortest paths, path having lower vertex_traversed_count will be chosen.

3. In this part, for the sake of distinguishing the paths operated by A and B airlines, we will keep all path prices of A airline as negative and for B as positive. Negative cost is only for distinguishing between airline A and B. For calculation of cost we will take mod of the negative values.

Algorithm:

1. Create a treeSet : Initially empty. It will contain all those vertices whose minimum cost from the source has been calculated.
2. Initially, all cost of the edges will be set to infinite and the cost of source vertex will be 0 so that it is selected as the source vertex.
3. Now, a loop till treeSet does not include the destination vertex.
             Steps in loop : i. Select the vertex x which has minimum cost from source. If it is not already added to the treeSet, add it to the treeSet.
ii. Now, update cost of all vertices which are connected to this x. Now, for all adjacent vertices, update their cost if it is less than the sum of cost from source vertex and the cost of edge between x and the adjacent vertex. (Only those adjacent
          vertex will be selected whose representational cost is different from previous ones.
                                        Like if came from negative cost vertex, we will include only positive cost vertex as
adjacent vertex.)