MATH EE HELP! PLEASE

[rohitreddy369]

HELP!!....I am a IBDP Student and Chose to do my EE in Mathematics. My Topic was Graph Theory, where I chose to find the least waiting time for passengers in my Local Metro Rail System. So far all I know is that I need to use Djkishtra's Algorithm. But I have no clue where to learn it from and also If anyone would help me in how to go about the EE..I would be very grateful.

[Vioh]

HELP!!....I am a IBDP Student and Chose to do my EE in Mathematics. My Topic was Graph Theory, where I chose to find the least waiting time for passengers in my Local Metro Rail System. So far all I know is that I need to use Djkishtra's Algorithm. But I have no clue where to learn it from and also If anyone would help me in how to go about the EE..I would be very grateful.

 

Hi, Dijkstra algorithm is part of the Discrete Mathematics option in Math HL course, so you should grab this book and try to learn it from there. I also took some notes about this algorithm when I did the option. You can access them here, then download the file "Math HL (Part 3).pdf". And Dijskstra algorithm is within the Table of Contents of that file.

 

Now, I am not sure how you want to approach your topic, but to give you an idea, I've drawn this diagram below, where A, B, C, D, E, F represent the train stations. For the line connecting between A & B, I wrote 5 + 2 = 7, which means that it takes total 7 minutes to get from A to B, with 5 minutes of waiting time at station A, and 2 minutes of sitting on the train.

 

So now, let's suppose you want to find the shortest time it takes from station A to station E. If you feed this problem into a computer, then the easiest algorithm that the computer can do is the brute force method. In other words, the computer will calculate the lengths of all the possible paths between A and E, and then compare them all to determine the shortest path. So for this diagram, the computer will have to calculate the total lengths of 4 different paths: ABCFE, ADE, ADFE, & ABCFDE.

 

Brute force is an exhaustive method, and would take a lot of time if the graph is huge. So Dijkstra provided a better way of looking for the shortest path. With Dijkstra's algorithm, the computer doesn't need to compute the lengths of all the possible paths between the 2 stations, because the algorithm also keeps track of the shortest path at the same time as it computes the lengths. This means that Dijkstra's algorithm takes much less time and computing power compared to the brute force method.

 

Hope this helps you getting started with your IA.