Programming_Contest

Problem 1: How many junctions' Problem description: The problem deals with the minimization of the path for a shipping problem. This problem deals with the delivery of large items where shipping becomes more complicated. When the path is larger, items are shipped from one city to another, and change shipping method at each location until they arrive to the wanted location. There are two costs related to transportation: 1- the cost of transportation between two cities and 2- the transshipping fees for any cargo passing through a city. A solution to this problem must find the shipping path with the least cost taking into consideration the two components of the transportation fee. Description of input The input consists of an integer m showing the number cases, followed for each case by the following: - An integer n which is the degree of the matrix - n lines holding costs describing the matrix - A line of n integers giving the transshipping cost of each city - A line of two integers which represent the source and the destination nodes. Description of output - The output shows the sequence of cities passed by and the total cost. |Sample Input |Sample Output | | | | |2 |From 1 to 3: | |5 |Path: 1-->5-->4-->3 | |0 3 22 -1 4 |Total cost: 21 | |3 0 5 -1 -1 | | |22 5 0 9 20 |From 1 to 3: | |-1 -1 9 0 4 |Path: 1-->2-->3 | |4 -1 20 4 0 |Total cost: 8 | |5 17 8 3 1 | | |1 3 | | | | | |3 | | |0 3 15 | | |3 0 3 | | |15 3 0 | | |2 2 2 | | |1 3 | | Description of the algorithm 1- The program starts by initializing the graph: a- Setting the number of edges to 0 b- Setting the number of vertices to 0 c- Initializing all the graph degrees to0 2- The program reads the matrix and inserts costs into the graph 3- The program stores the transshipment fees of the different cities. 4- The program calls the dijkstra function to find the total minimal cost of the shipping path. a- Set all intrees to 0 b- Set all distances to infinity c- Set all parents to -1 d- Set the distance at the source vertex to 0 e- Walk through trees, add the tree any edge not contained in it yet f- Find the candidate edge w g- Set the weight of the candidate edge h- if the distance from start to the vertex v added + the weight of the edge added + the transshipment fees of w is smaller than the distance from the start to w, then it becomes the new distance i- the max distance is computed 5- The function findPath is called to return the minimal path. This function works on inverting the array containing the parents Time Complexity The time complexity of the graph can be determined by the following: - The time complexity of Djikstra shortest path is Θ(v2), ((e), where v is the number of vertices and e is the number of edges - The time complexity of reading a graph and inserting edges is O(v²) ← The time complexity of the algorithm is O(v²) Problems Encountered We encountered big problems when trying to solve this problem. The main difficulty was to implement the Dijkstra shortest path algorithm. It took us significant time trying to do that. Fortunately, we were told by one of our classmates that the solution already exists in the algorithm challenges book. Finally, we borrowed most of our code from the code existing in the book. Overall, we have noticed that graph problems are very challenging to solve, but very useful in minimizing paths in real life applications. [pic]