Dijkstra's algorithm| Predict petrol explosion| Shortest path| Scaled model verification| Algorithm|

Chapters of this video: Introduction: 00:00 - 00:20 Problem statement: 00:21 - 00:33 Natural way of solving: 00:34 - 02:49 Dijkstra's algorithm: 02:50 - 03:31 Algorithmic way of solving: 03:32 - 07:53 Practical demonstration: 07:54 - 08:25 Some issues: 08:26 - 08:46 Scaled model: 08:47 - 09:49 Lecture transcription(Algorithm part): Our starting point is Chennai which is burnt. The fire has now reached Chennai, so the shortest distance between Chennai to Chennai is zero. we don't know about the other stations yet, so we update the first row of the table - the distance between Chennai and Chennai is 0, and the distances to other stations are infinity. The fire is going to spread. From Chennai, three pipelines directly connect to three other headquarters - Trichy which is 332 km away, Sankari 380 km away, and Kochi 690 km away. So the fire will first reach Trichy and burn that headquarters. But at the same time, the fire will also pass through the other two pipes and cover a distance of 332 km. In the second row of the table, we update the respective distances from Chennai to the other stations - Trichy 332 km, Sankari 380 km, and Kochi 690 km. Here, the minimum distance is Trichy, so Trichy will be burnt first. The fire is now in Trichy, and Trichy connects to two other headquarters - Karur and Madurai. So the total distance the fire reaches Karur from Chennai is 332 km + 82 km = 414 km, and for Madurai is 471 km. we update the third row of the table with the known distances with respect to Chennai. Trichy has already burnt, so we leave that. Sankari is 380 km away, Kochi is 690 km away, Karur is 414 km away, and Madurai is 471 km away. Here, the minimum distance from Chennai is 380 km, which means Sankari is going to burst next. Now, the fire is in Sankari, and we have a pipeline connection to Karur. So the total distance from Chennai to Karur via Sankari is 380 km + 70 km = 450 km. we already have another pipeline connection reaching Karur via Trichy which is 414 km. So, the fire will reach Karur via the path with the minimum distance, which is 414 km. Next, we update the respective known distances in row 4. Karur is 414 km, Madurai is 471 km, and Kochi is 690 km. The minimum distance is 414 km, so the next burnt headquarters is Karur. Now, the fire is in Karur, and we have some pipeline connections. The newly obtained information is the distance to Coimbatore. So, the total distance from Chennai to Coimbatore based on this path is 414 km + 131 km = 545 km. we update the next row with the known distances - Madurai is 471 km, Coimbatore is 545 km, and Kochi is 690 km. The minimum distance is Madurai, which is 471 km. So the next burnt headquarters is Madurai. Now, the fire is in Madurai, and from Madurai, there is a path to Coimbatore with a distance of 217 km. So the total distance is 471 km + 217 km = 688 km. We already know another path to Coimbatore via Karur, which is only 545 km. So we take the minimum distance, which is 545 km. we update the known distances in the table - 545 km for Coimbatore and 690 km for Kochi. The minimum distance is 545 km, which means Covai will be the next location to be burnt. Now that the fire is in Covai, there is a path to Kochi. The total distance via Covai is 545 km + 190 km = 735 km. We know there is another path that has a distance of 690 km. Therefore, we take the minimum distance of 690 km, and that is the last headquarters that is 690 km away from Chennai, which will be burnt next. Using Dijkstra's Algorithm, we get the sequence of burnt headquarters: Chennai → Trichy → Sankari → Karur → Madurai → Covai → Kochi. #dijkstra #graphtheory #scaledmodel #algorithm #maths #practicalmaths