Take up the challenge and win great prizes!

#3 Challenge: Now it's getting trickier!
Shortest path with Dijkstra

Time required: Approx. 40-60 minutes

We're sure you have successfully tackeled challenges 1 and 2! Now it's getting a bit trickier! Are you up for the challenge? 

Sometimes we have to find the quickest way through a labyrinth of possibilities. Certain algorithms can model this, for example when modeling a traffic network or various Internet protocols. We have a few exercises for you to test your problem-solving skills. Can you find the shortest route?

With a bit of luck, you could win a 150 CHF voucher from Galaxus!

Question 1

Sarah from our Zurich office has a full day today. First, she has a personal meeting with her colleagues for an innovation project in Zurich. Then, she has a client meeting in Basel and takes the opportunity to drop by the Basel office and say hello to the Basel team. Finally, she heads to the IoT Hack Night at the Bern office to round off the evening with an IoT challenge over pizza and a few beers.

What’s the quickest way for Sarah to get from the ti&m office in Zurich to the ti&m office in Bern, if she stops by and says hello to her colleagues at the ti&m office in Basel first?

Question 2

A new employee of a client company has opened an unsafe email and now the entire system is infected with a worm. The ti&m security team must gain access to all computers and clean them individually. The time costs for taking over control are indicated by the arc. 
 
ti&m relies on you to take back the control of all the devices, but don’t be afraid, you are not alone! You can at any time ask one or more ti&m colleagues to help you with the other nodes while you are working on your node – what is important to the client is that it must be done in the fastest way possible. 

Question: What is the minimum time to take back the control of all devices? This should correspond to the time of the longest path (as in that time your colleagues have already cleared all the other devices)

Bonus hint for question 2

Need a hint?: In the example you can see the tricky part. There are two ways to get from S to B. The time to arrive to B on the example 1 on the left (7) is shorter than on the example 2 on the right (9). That is the shortest path. However, the total cost (the sum of all the archs used to reach all nodes) will be higher on the example 1 on the left (10) as on the example 2 on the right (9).