[SOLVED] CSE221 Lab 4

Problems Description:

The following tasks need to be solved using Shortest path algorithms.In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized. You have learned several shortest path algorithms such as Dijkstra’s algorithm, Bellman-Ford algorithm etc. The problems below are related or similar to some of the shortest path algorithms you learned in class.

Read the task descriptions carefully and implement the algorithm using either Java or Python or any language you are comfortable with. The output format MUST match exactly as shown in each task.

TASK 1 [5 Marks]

Oh No! Wall Maria is Breached! Titans (human eating creatures) are coming. Eren has to reach his home as soon as possible to save his mother.

For simplicity, let’s think of Eren’s hometown map containing N places and M roads. A road is a connection between two places.Here, each place is represented by a unique number between 1 and N.

Suppose, each road is represented by i and each ith road connects 2 places ui and vi (ui and vi are the unique number of the places) and this road is overrun by wi titans. You can assume Eren’s current position as 1 and Eren’s home as N. Now help Eren to find a path so that he has to face as minimum number of titans as possible.

For example, in the following graph (vertices represent places and edges represent roads), Eren has to face a minimum 5 titans by using the path 1 → 4 → 3 → 5.

Input Format:
First line contains a number T which represents the number of test cases. For each test case:

First line will contain 2 numbers N, M representing the number of places and roads respectively.

Each of the following M lines will contain 3 numbers ( ui vi wi ) representing one of the roads that connects places ui, vi and is guarded by wi titans.

Output Format:

For each test case, print one number which will be the minimum number of titans Eren has to face to reach his home. It is ensured that there exists roads connecting Eren’s current position to his home.

Sample Input:

3
10 21
1 2 10 56

3 51 1 21 2 34 1 42 4 32 2 55

Sample Output:

0 10 5

Sample Description:

Here we have 3 test cases.

In the 1st case, there is 1 place and 0 roads. So, Eren is already at home, i.e. he has to face 0 titans.

In the 2nd case, there are 2 places and 1 road connecting them which is guarded by 1 10 titans. So, Eren has to face 10 titans to reach home.

In the 3rd case, the example graph shown before is given. For that, it was shown that Eren has to face at least 5 titans.

Hint 1:

function Dijkstra(𝐺𝑟𝑎𝑝h, 𝑠𝑜𝑢𝑟𝑐𝑒):
𝑑𝑖𝑠𝑡[𝑠𝑜𝑢𝑟𝑐𝑒] ← 0 // Initialization

create a priority queue 𝑄for the vertices // min-heap create a list 𝑣𝑖𝑠𝑖𝑡𝑒𝑑 for the vertices
for each vertex 𝑣 in 𝐺𝑟𝑎𝑝h:

if 𝑣 ≠ 𝑠𝑜𝑢𝑟𝑐𝑒:
𝑑𝑖𝑠𝑡[𝑣] ← ∞ // Unknown distance from 𝑠𝑜𝑢𝑟𝑐𝑒 to 𝑣 𝑝𝑟𝑒𝑣[𝑣] ← ␀ // Predecessor of 𝑣

add 𝑣 to 𝑄 with priority value 𝑑𝑖𝑠𝑡[𝑣] 𝑣𝑖𝑠𝑖𝑡𝑒𝑑[𝑣] ← 𝐹𝑎𝑙𝑠𝑒

You can use the following pseudocode of Dijkstra’s algorithm.

while 𝑄 is not empty:
𝑢 ← 𝑄.extract_min()

if 𝑣𝑖𝑠𝑖𝑡𝑒𝑑[𝑢]: continue

𝑣𝑖𝑠𝑖𝑡𝑒𝑑[𝑢] ← 𝑇𝑟𝑢𝑒

// The main loop
// Remove and return best vertex

for each neighbor 𝑣 of 𝑢:
𝑎𝑙𝑡 ← 𝑑𝑖𝑠𝑡[𝑢] + 𝑙𝑒𝑛𝑔𝑡h(𝑢, 𝑣) if 𝑎𝑙𝑡 < 𝑑𝑖𝑠𝑡[𝑣]:

𝑑𝑖𝑠𝑡[𝑣] ← 𝑎𝑙𝑡
𝑝𝑟𝑒𝑣[𝑣] ← 𝑢
add 𝑣 to 𝑄 with priority value 𝑑𝑖𝑠𝑡[𝑣]

return 𝑑𝑖𝑠𝑡, 𝑝𝑟𝑒𝑣

Note:

●

●

Hint 2:

Min-heap data structure is used to implement the priority queue. There are libraries that implement this.

What are you supposed to return for problem 1? Do you need to compute 𝑝𝑟𝑒𝑣?

Hint 3:

Hint 4:
Try to incorporate wi’s into the adjacency list.

Use adjacency list representation of Graph while reading from input.

TASK 2 [5 Marks]

Modify your code for the first problem to find the path Eren has to follow to face the minimum number of titans.

For the previous sample input, the output is:

1
12
1 435

Sample Description:

Here we have 3 test cases.

In the 1st case, there is 1 place and 0 roads. So, Eren is already at home, i.e. the path is: 1.

In the 2nd case, there are 2 places and 1 road connecting them which is guarded by 1 10 titans. So, the path to face minimum titans is the only existing path: 1 → 2.

In the 3rd case, the example graph shown before is given. For that, it was shown that, to face the minimum number of titans, Eren has to follow the path: 1 → 4 → 3 → 5.

TASK 3 [1.5+ 1.5 + 2 = 5 Marks]

If there are 𝑁 places and 𝑀 roads, what are the time complexities of the solutions you provided in problem 1 & problem 2 respectively?
If the number of titans in each road is exactly 1, there is an 𝑂(𝑁 + 𝑀) algorithm to solve this problem. What is it?

Note: If you can use any known algorithm, write its name and the inputs that will be given to it. Otherwise, give a pseudocode of the algorithm.

TASK 4 [10 Marks]
In a computer network, there are N devices and M links. A link is a one way connection

from one device to another. Each link has a data transfer rate d it can support.

The data transfer rate of a connection from one device to another is the minimum data transfer rate of the links in that connection. [You can think of connection as a directed path. So, a connection from device u to device v is a sequence of links that joins a sequence of distinct devices where the links are directed from u to v.]

For example, in the network above, there can be three possible connections from 1 to 4:

(i) 1 → 2 → 4 : alt = 3
(ii) 1 → 3 → 4: alt = 2>3 (iii) 1 → 3 → 2 → alt = 6 >3

In connection (i), there are two links: 1 → 2 with data rate 3, 2 → 4 with data rate 7. So, data transfer rate of this connection is minimum of 3 and 7, that is 3.
Similarly, data transfer rate of connection (ii) and (iii) are 2 and 6 respectively.

Now, the maximum data transfer rate from a device u to a device v is the maximum of the data transfer rates of all possible connections from u to v. For example, the maximum data transfer rate from 1 to 4 that this network supports is 6 (through connection (iii)).

Now, given a computer network, you have to calculate the maximum data transfer rate this network supports from a designated source device to all other devices.

Input Format :
First line contains a number T which represents the number of test cases.

For each test case:

First line contains 2 numbers N, M representing the number of devices and links respectively.

Each of the following M lines will contain 3 numbers ( ui vi di ) representing a link from device ui to device vi with data transfer rate di.
The last line contains a number s, which is the source device.

Output Format :

For each test case, print a list of numbers, where 𝑖𝑡h number represents the maximum data transfer rate from s to i.
Note: print 0 when s == i and print -1 if there is no connection from s to i.

Sample Input: 4
10
1

21 1 21 1 21 1 21 2 45 3 26

1. 1  23
2. 2  47
3. 3  42

1 38 1

Sample Output: 0
01
-1 0

0 686

Sample Description:

Here we have 4 test cases.

In the 1st case, there is 1 device and 0 links, so there is no edge. Here the source device is 1. As the maximum data transfer rate between device 1 to 1 itself is 0, the output is 0.

In the 2nd case, there are 2 devices and 1 link. Here the source device is 1. From device 1→1 the data transfer rate is 0. The maximum data transfer rate between 1→ 2 devices is 1 (As there is only 1 data rate). So the output is 0 1.

In the 3rd case, there are 2 devices and 1 link. Here the source device is 2. From the input we can see that there is a connection between 1→ 2 with a data transfer rate of 1. but there is no connection between 2→1. So, from 2→1 the output will be -1 as noted above in the output format. And for 2→2 the output will be 0. So, the output is -1 0.

In the 4th test case, the example graph is given. Here the source device is 1. From 1→1, output is 0. From device 1 to device 2 there can be 2 possible paths, 1→2 and 1→3→2. The maximum data transfer rate for 1→2 will be 6 if we consider this path 1→3→2. Similarly, From 1→3, there is only one path and the data transfer rate is 8, so output is 8. For 1→4 the example is given in the beginning. So the output is 0 6 8 6.

Hint:

1. In the shortest path problem, you calculate path length by summing all edgeweights in the path. Whereas in this problem you need to calculate data transfer

   rate which is obtained by taking the minimum of all edge weights in the path.

2. In the shortest path problem, you are trying to minimize path length, whereas inthis problem you are trying to maximize data transfer rate.
   [In Dijsktra’s algorithm, initialize 𝑑𝑖𝑠𝑡 array differently and change the codes related to priority queue for maximization]

You can use the following pseudocode which is based on these hints. function Network(𝐺𝑟𝑎𝑝h, 𝑠𝑜𝑢𝑟𝑐𝑒):

𝑑𝑖𝑠𝑡[𝑠𝑜𝑢𝑟𝑐𝑒] ← ∞ // Initialization
create a priority queue 𝑄for the vertices // Max-priority Queue for each vertex 𝑣 in 𝐺𝑟𝑎𝑝h:

if 𝑣 ≠ 𝑠𝑜𝑢𝑟𝑐𝑒:
𝑑𝑖𝑠𝑡[𝑣] ← − ∞ // Unknown data transfer rate from 𝑠𝑜𝑢𝑟𝑐𝑒 to 𝑣 𝑝𝑟𝑒𝑣[𝑣] ← 𝑁𝑈𝐿𝐿 // Predecessor of 𝑣

add 𝑣 to 𝑄 with priority value 𝑑𝑖𝑠𝑡[𝑣]
while 𝑄 is not empty: // The main loop

𝑢 ← 𝑄.extract_max() // Remove and return best vertex for each neighbor 𝑣 of 𝑢:

𝑎𝑙𝑡 ← 𝑚𝑖𝑛(𝑑𝑖𝑠𝑡[𝑢], 𝑙𝑒𝑛𝑔𝑡h(𝑢, 𝑣)) if 𝑎𝑙𝑡 > 𝑑𝑖𝑠𝑡[𝑣]:

𝑑𝑖𝑠𝑡[𝑣] ← 𝑎𝑙𝑡
𝑝𝑟𝑒𝑣[𝑣] ← 𝑢
add 𝑣 to 𝑄 with priority value 𝑑𝑖𝑠𝑡[𝑣]

return 𝑑𝑖𝑠𝑡, 𝑝𝑟𝑒𝑣

Note: The libraries for priority queue may only implement min-heap data structure. But for this problem, we need a max-heap.