Tip:
Highlight text to annotate it
X
- WELCOME TO A LESSON ON DIJKSTRA'S ALGORITHM.
WHEN YOU VISIT A WEBSITE LIKE GOOGLE MAPS
OR USE YOUR SMART PHONE FOR DRIVING DIRECTIONS
YOU'RE USUALLY LOOKING FOR A SHORTEST PATH
BETWEEN TWO LOCATIONS.
THESE COMPUTER APPLICATIONS USE REPRESENTATIONS
OF THE STREET MAPS AS GRAPHS,
WITH THE ESTIMATED DRIVING TIMES AS EDGE WEIGHTS.
OFTEN IT IS POSSIBLE TO FIND A SHORTEST PATH ON A SMALL GRAPH
BY USING GUESS AND CHECK.
HOWEVER, OUR GOAL IS TO DEVELOP METHODS
TO SOLVE COMPLEX PROBLEMS IN A SYSTEMATIC WAY
BY FOLLOWING ALGORITHMS.
AN ALGORITHM IS A STEP BY STEP PROCEDURE FOR SOLVING A PROBLEM.
DIJKSTRA'S ALGORITHM WILL FIND THE SHORTEST PATH
BETWEEN TWO VERTICES.
AND HERE ARE THE STEPS WE'LL FOLLOW.
NUMBER ONE, WE'LL MARK THE ENDING VERTEX
WITH A DISTANCE OF ZERO,
DESIGNATE THIS VERTEX IS CURRENT.
TWO, WE'LL FIND ALL THE VERTICES LEADING TO THE CURRENT VERTEX,
CALCULATE THEIR DISTANCES TO THE END.
SINCE WE ALREADY KNOW THE DISTANCE THE CURRENT VERTEX
IS FROM THE END,
THIS WILL JUST REQUIRE ADDING THE MOST RECENT EDGE.
WE DON'T RECORD THIS DISTANCE
IF IT IS LONGER OR LARGER THAN A PREVIOUS RECORDED DISTANCE.
THREE, WE'LL MARK THE CURRENT VERTEX AS VISITED
AND WE'LL NEVER LOOK AT THIS VERTEX AGAIN.
AND THEN FOUR,
WE MARK THE VERTEX WITH THE SMALLEST DISTANCE AS CURRENT
AND REPEAT FROM STEP TWO.
FINALLY FIVE, STOP ONCE YOU FOUND THE SHORTEST DISTANCE
FROM THE STARTING TO THE ENDING VERTEX.
SO LET'S TAKE A LOOK AT AN EXAMPLE.
WE WANT TO FIND THE SHORTEST PATH BETWEEN VERTICES "A" AND G
USING THE GRAPH.
SO WE'RE GOING TO WORK BACKWARDS FROM G
AND FIND THE SHORTEST PATH TO "A".
THOUGH, IT REALLY WOULDN'T MATTER IF WE STARTED WITH "A"
AND FIND THE SHORTEST PATH TO G.
SO WE'LL MARK VERTEX G WITH A ZERO
INDICATING THAT ZERO UNITS FROM THE END.
AND WE'LL ALSO LABEL G AS CURRENT.
NOW WE'LL LOOK AT ALL THE VERTICES THAT LEAD TO G,
WHICH WOULD BE E AND F IN THIS CASE.
WELL, NOTICE E WOULD BE 7 UNITS FROM G,
SO WE'LL LABEL E WITH A 7.
AND NOTICE THAT F IS 6 UNITS FROM G,
SO WE'LL LABEL F WITH A 6.
SO NOW WE CAN MARK G AS VISITED.
SO WE'LL SAY THIS MEANS IT'S VISITED.
AND BECAUSE 6 IS LESS THAN 7 VERTEX F IS NOW CURRENT.
AND NOW WE'LL LOOK AT ALL THE VERTICES THAT LEAD TO F.
NOTICE THAT E LEADS TO F, BUT SINCE 6 + 2 = 8
AND WE ALREADY HAVE E LABELED AS 7, WE WON'T RECORD THIS VALUE.
BUT D ALSO LEADS TO F, AND SINCE 6 + 4 = 10
WE'LL LABEL D WITH 10
TO REPRESENT D AS 10 UNITS FROM THE END.
C ALSO LEADS TO F.
NOTICE 6 + 5 = 11, SO WE'LL MARK C AS 11.
NOW WE CAN MARK F AS VISITED.
SO WE LOOKING AT VERTEX E, D, AND C,
SINCE E IS THE LEAST DISTANCE FROM THE END E IS NOW CURRENT.
AND NOW WE'LL LOOK AT ALL THE VERTICES LEADING TO E,
WHICH SHOULD BE B AND D BECAUSE WE ALREADY VISITED F.
FIRST LOOKING AT VERTEX B, NOTICE 7 + 6 = 13,
SO WE LABEL VERTEX B WITH 13
MEANING ITS 13 UNITS FROM THE END.
NOW LOOKING AT VERTEX D, NOTICE HOW 7 + 2 = 9
WHICH IS LESS THAN 10, SO WE'D REPLACE 10 WITH 9,
MEANING IF WE TAKE THIS PATH D IS ONLY 9 UNITS FROM THE END.
WE MARK E AS VISITED.
LOOKING AT VERTEX B, D, AND C,
NOTICE HOW D IS THE LEAST DISTANCE FROM THE END,
SO D IS CURRENT.
AND NOW WE LOOK AT THE VERTICES LEADING TO D,
WHICH WOULD BE B AND C.
LOOKING AT B FIRST, NOTICE HOW 9 + 3 = 12.
BECAUSE 12 IS LESS THAN 13 WE REPLACE 13 WITH 12.
LOOKING AT C, NOTICE THAT 9 + 2 = 11.
SINCE C IS ALREADY MARKED WITH 11
WE CAN GO AHEAD AND LEAVE THAT AS 11.
WE'LL MARK D AS VISITED.
LOOKING AT VERTICES B AND C, BECAUSE 11 IS LESS THAN 12
C IS NOW CURRENT.
LOOKING AT THE VERTICES THAT LEAD TO C WHICH IS ONLY "A,"
NOTICE THAT 11 + 4 = 15, SO WE MARK "A" AS 15
MEANING IF WE FOLLOW THIS PATH "A" IS 15 UNITS FROM G.
WE MARK C AS VISITED.
AND SINCE 12 IS LESS THAN 15 VERTEX B IS NOW CURRENT.
ONLY VERTEX "A" LEADS TO B, AND SINCE 12 + 1 = 13
WHICH IS LESS THAN 15
WE REPLACE 15 WITH 13 GIVING US OUR SHORTEST PATH.
SO B IS NOW VISITED AND WE'RE DONE.
SO THE SHORTEST PATH FROM "A" TO G IS 13 UNITS
AND THAT PATH WOULD BE "A" TO B, B TO D, D TO E,
AND FINALLY E TO G.
THIS IS AN EXAMPLE OF DIJKSTRA'S METHOD
OF FINDING THE SHORTEST PATH.
I HOPE YOU FOUND THIS HELPFUL.