1
00:00:07,200 --> 00:00:14,040
In this lecture, we're going to begin going over a possible implementation for Dijkstra's algorithm.

2
00:00:14,520 --> 00:00:18,270
Now, there are many ways that Dijkstra's algorithm can be implemented.

3
00:00:18,270 --> 00:00:26,760
So I encourage you after this lecture to potentially think of other ways and methods that we would be

4
00:00:26,760 --> 00:00:29,070
able to implement in this algorithm.

5
00:00:29,700 --> 00:00:34,950
So before going over the implementation, we need to do a bit of setup.

6
00:00:35,640 --> 00:00:40,620
The first thing that I want you to do is just go ahead and comment out everything that we did from depth

7
00:00:40,620 --> 00:00:42,780
for search and breadth for search.

8
00:00:42,780 --> 00:00:47,670
That way we don't have any conflicting types possible.

9
00:00:48,690 --> 00:00:55,530
And then once you do that, we need to do a bit of setup before we can begin implementing in the Dijkstra's

10
00:00:55,530 --> 00:00:56,210
algorithm.

11
00:00:56,220 --> 00:00:59,430
So the first thing that we need to do is bring some stuff into scope.

12
00:01:00,090 --> 00:01:09,210
So we're going to bring in ordering and then we're also going to bring in the binary heap collection.

13
00:01:12,810 --> 00:01:17,970
Next, we want to derive a few things for the structure that we're going to create.

14
00:01:17,970 --> 00:01:24,510
We're going to derive copy, clone and partial equality.

15
00:01:25,410 --> 00:01:33,480
And now we can create our struct and we'll call it state, and it's going to have a field of cost of

16
00:01:33,480 --> 00:01:39,120
type use, size and position of type you size as well.

17
00:01:43,020 --> 00:01:53,100
So now we want to implement Ord for state, so we'll say implement Ord for state.

18
00:01:53,100 --> 00:02:04,080
So we're implementing ordering for state and we will say F in compare and self and then other.

19
00:02:06,670 --> 00:02:18,860
With a reference to self as well, where we return ordering and what we'll do is we will say other costs

20
00:02:18,970 --> 00:02:23,560
dot compare and self cost.

21
00:02:23,560 --> 00:02:30,760
So you can see where this is going, where we're comparing the weight of the edge and then if there

22
00:02:30,760 --> 00:02:36,130
happened to be equal, then we will just compare their positioning.

23
00:02:36,850 --> 00:02:45,400
So we will say self, dot position, dot compare and other dot position.

24
00:02:47,800 --> 00:02:48,400
All right.

25
00:02:48,400 --> 00:02:54,490
So we are comparing the cost, aka the weights.

26
00:02:54,490 --> 00:02:56,860
And then if the.

27
00:02:58,110 --> 00:03:01,980
Costs are the same than we want to compare their positions.

28
00:03:04,320 --> 00:03:05,060
All right.

29
00:03:05,070 --> 00:03:06,600
What do we have here?

30
00:03:10,590 --> 00:03:14,230
It looks like we need to implement partial equality as well.

31
00:03:14,250 --> 00:03:24,720
So we will say in full or partial aud excuse me, partial aud four state and we will say if in partial

32
00:03:24,720 --> 00:03:32,490
compare, and it sets all of that up for us and we will say self dot compare other.

33
00:03:33,420 --> 00:03:38,640
So that was a really easy one for us to set up and that one just need to be implemented as well.

34
00:03:40,110 --> 00:03:51,030
So now we can set up the edge struct, so we will say struct edge where we will have node you size and

35
00:03:51,030 --> 00:03:53,490
cost you size.

36
00:03:56,280 --> 00:04:03,150
And that's all we have to do in terms of setting up for what we're looking to do.

37
00:04:05,640 --> 00:04:09,630
So now we can begin implementing in Dijkstra's algorithm.

38
00:04:09,630 --> 00:04:17,040
So we're going to start obviously at a starting vertex and then we're going to keep track of the distance

39
00:04:17,940 --> 00:04:19,170
to each node.

40
00:04:20,550 --> 00:04:32,820
So what we can do is say shortest path and we will pass in our graph and we will.

41
00:04:34,110 --> 00:04:42,630
And our graph is going to be a vector that a reference to a vector that contains a vector that contains

42
00:04:42,630 --> 00:04:43,590
the edge.

43
00:04:45,720 --> 00:04:54,090
We will have start, which is you size, and then we will have goal, which is also use size and we

44
00:04:54,090 --> 00:04:58,160
will return an option of type size.

45
00:04:58,170 --> 00:05:06,840
So what we're going to return is the overall cost for us to get from our start to our goal.

46
00:05:08,910 --> 00:05:11,520
And we will return none that way.

47
00:05:11,520 --> 00:05:13,830
We don't have any red squiggles anywhere.

48
00:05:14,070 --> 00:05:19,410
And so the first thing we want to do is keep track of the distances.

49
00:05:19,410 --> 00:05:25,770
So we will say let meet distance is equal to vector of a type that we don't care about.

50
00:05:26,850 --> 00:05:40,680
And we will say from zero to graph dot length map these values that we do not care about.

51
00:05:40,680 --> 00:05:47,400
And we will say you size max dot.

52
00:05:48,270 --> 00:05:49,010
Correct.

53
00:05:49,890 --> 00:06:00,150
So what we are doing here is saying, hey, for all of our distance, go ahead and make them the max

54
00:06:00,150 --> 00:06:00,630
size.

55
00:06:00,630 --> 00:06:06,270
That way, when we look at the actual distance, we get a good comparison of.

56
00:06:07,310 --> 00:06:08,840
What we want, right?

57
00:06:08,840 --> 00:06:16,040
So if it's you size max, then when we compare it to the distance inside of our vector here, we'll

58
00:06:16,040 --> 00:06:20,630
be able to update that accordingly with the edges cost.

59
00:06:22,670 --> 00:06:33,530
So now we want to create our visited and we will say binary heap new.

60
00:06:34,490 --> 00:06:41,360
So we know that our starting distance is always going to be zero because that is where we starting at

61
00:06:41,750 --> 00:06:47,960
and we will push this into visit it since that is where we are currently at.

62
00:06:47,960 --> 00:06:56,120
So we will say state our cost is zero and our position is start.

63
00:06:59,080 --> 00:06:59,680
All right,

64
00:07:02,500 --> 00:07:11,950
So now we can examine the other nodes or excuse me, the other vertices with the lowest cost.

65
00:07:11,950 --> 00:07:15,310
So we will say while at some

66
00:07:17,350 --> 00:07:27,100
state of cost position equals visited dot pop.

67
00:07:28,540 --> 00:07:33,190
So now we need to check to see if the position we're at is the goal.

68
00:07:33,190 --> 00:07:41,950
So if position is equal to our goal, then we just want to go ahead and return some cost.

69
00:07:41,950 --> 00:07:49,090
And that cost is going to be our distance to get from our starting to our goal.

70
00:07:50,950 --> 00:07:59,710
Otherwise, if our cost is greater than our current distance, well then we've already found a better

71
00:07:59,710 --> 00:08:00,040
way.

72
00:08:00,040 --> 00:08:02,320
So we can just go ahead and say continue.

73
00:08:05,050 --> 00:08:13,150
And then otherwise, for each node that we can reach, we need to check to see if there is a way forward

74
00:08:13,150 --> 00:08:16,750
with a lower cost going through that node.

75
00:08:16,750 --> 00:08:21,340
So we can save for edge in our graph

76
00:08:24,670 --> 00:08:26,470
with our current position.

77
00:08:27,370 --> 00:08:42,370
Then we need to say next is equal to state cost of cost plus edge cost and position of edge node.

78
00:08:44,650 --> 00:08:57,280
So if our next cost is less, so if next dot cost is less than our current dist next position.

79
00:08:58,320 --> 00:08:59,760
Then we found a better way.

80
00:09:01,080 --> 00:09:06,030
So we will say visited dot push next.

81
00:09:08,840 --> 00:09:23,510
And now that we have found a better way, we will say dist next dot position is equal to next dot cost.

82
00:09:26,690 --> 00:09:34,700
So that's all we need to do to implement the shortest path here, and we return none still down here.

83
00:09:34,700 --> 00:09:39,800
In the event that there is no way for us to get from start to our goal.

84
00:09:39,800 --> 00:09:47,540
So if we say get to some vertex that does not exist in the graph, then we want to return none because

85
00:09:47,540 --> 00:09:49,730
we don't have a path to it.

86
00:09:50,090 --> 00:09:57,860
So now we can test this out and we'll test this out by using the graph we created in our previous lecture.

87
00:09:57,860 --> 00:10:02,420
That way we can very clearly identify if this is working or not.

88
00:10:02,420 --> 00:10:08,090
So we will say mod test, use super on everything.

89
00:10:08,090 --> 00:10:14,900
That way we can bring it all into scope and we will say Test

90
00:10:17,750 --> 00:10:18,620
Dykstra.

91
00:10:19,340 --> 00:10:22,160
And then here, now we can create our graph.

92
00:10:22,940 --> 00:10:28,460
So we will say let graph is equal to a VEC.

93
00:10:31,070 --> 00:10:37,550
And then inside of our vec we're going to have obviously another VEC and our vec is going to contain

94
00:10:37,550 --> 00:10:44,570
an edge going from node one, cost six.

95
00:10:54,660 --> 00:10:55,170
Vic?

96
00:10:56,610 --> 00:10:56,970
Nope.

97
00:10:57,000 --> 00:10:57,750
Excuse me.

98
00:10:57,780 --> 00:11:03,150
Edge of Node two cost.

99
00:11:04,960 --> 00:11:05,770
For.

100
00:11:07,320 --> 00:11:12,440
And I need to add in that guy, Tim.

101
00:11:14,080 --> 00:11:18,480
It helps if I add in everything appropriately.

102
00:11:18,480 --> 00:11:19,080
There we go.

103
00:11:20,100 --> 00:11:25,680
And we will add in one more edge of Node three.

104
00:11:26,010 --> 00:11:27,570
Cost one.

105
00:11:30,830 --> 00:11:38,540
Now we will add another vector and we can start copying and pasting.

106
00:11:39,290 --> 00:11:41,060
To speed these up.

107
00:11:41,660 --> 00:11:47,030
So this vector will go from node zero.

108
00:11:49,070 --> 00:11:50,090
Two six.

109
00:11:52,490 --> 00:11:55,400
And we will go from node to.

110
00:11:57,270 --> 00:11:58,230
To three.

111
00:11:59,310 --> 00:12:08,250
So what we're doing here again is we are recreating our graph from the previous lecture where we learned

112
00:12:08,250 --> 00:12:11,340
to see how Dijkstra's algorithm worked.

113
00:12:11,910 --> 00:12:23,220
So now we're going from Node 0 to 4, and I know we didn't have a Node zero in the previous lecture,

114
00:12:23,820 --> 00:12:35,940
but remember, vertex indexes start at zero, so subtract one from all of our vertex nodes in the previous

115
00:12:35,940 --> 00:12:43,080
lecture, so vertex one would become zero for text to becomes one, and so on and so forth.

116
00:12:44,760 --> 00:12:49,350
We can let's go format this just to make it easier to read.

117
00:12:49,860 --> 00:12:50,670
There we go.

118
00:12:52,530 --> 00:12:52,890
All right.

119
00:12:52,890 --> 00:13:01,350
So in our Node two, technically we go from zero from node 2 to 0 with a cost of four.

120
00:13:01,920 --> 00:13:03,030
We go from.

121
00:13:03,060 --> 00:13:06,090
To node one with a cost of three.

122
00:13:06,090 --> 00:13:09,000
And remember, it's un directed.

123
00:13:09,000 --> 00:13:14,100
So we want to make sure we have all of our edges going both ways.

124
00:13:14,100 --> 00:13:19,920
And then we go to Node three with a cost of one.

125
00:13:26,830 --> 00:13:29,650
And add a comma here.

126
00:13:29,890 --> 00:13:31,720
And our last node.

127
00:13:38,360 --> 00:13:41,150
We have our edge.

128
00:13:42,040 --> 00:13:43,780
You don't need those.

129
00:13:44,110 --> 00:13:58,180
Our edge going from zero to to zero with a cost of one and our other edge going to node two with a cost

130
00:13:58,180 --> 00:13:58,690
of one as well.

131
00:13:58,690 --> 00:14:00,540
So let's run cargo format again.

132
00:14:00,550 --> 00:14:01,150
All right.

133
00:14:01,300 --> 00:14:02,650
So that looks a lot better.

134
00:14:02,650 --> 00:14:09,340
So what we have here is to make this clear, this is Node zero.

135
00:14:11,920 --> 00:14:14,410
Node one.

136
00:14:16,480 --> 00:14:17,170
No.

137
00:14:17,200 --> 00:14:22,360
Two and Node three.

138
00:14:22,990 --> 00:14:30,820
So here we have Node zero going to one with a cost of six, node zero going to two with a cost of four

139
00:14:30,850 --> 00:14:35,710
0 to 3, with a cost of one, 1 to 0 cost of six.

140
00:14:35,710 --> 00:14:40,990
So that way you can see that it is undirected, it is an undirected graph.

141
00:14:41,890 --> 00:14:49,150
And again, this is the same exact graph that we did in our previous lecture.

142
00:14:49,150 --> 00:14:56,800
So if you need a refresher on what this graph looks like visually, feel free to just to go rewatch

143
00:14:56,800 --> 00:14:57,670
that lecture.

144
00:14:57,670 --> 00:14:59,560
That way you can see what it looks like.

145
00:15:00,250 --> 00:15:04,210
And so now we can say assert equals and we want to call

146
00:15:07,000 --> 00:15:09,130
what did we call our function up here?

147
00:15:09,460 --> 00:15:10,900
Shortest path.

148
00:15:12,340 --> 00:15:15,220
So we say shortest path pass in our graph.

149
00:15:16,120 --> 00:15:19,420
Our start we will say is zero.

150
00:15:19,660 --> 00:15:23,950
And our goal is we want to get to Node one

151
00:15:26,590 --> 00:15:27,580
and

152
00:15:29,980 --> 00:15:38,590
Q So what we're expecting to be returned here is some five.

153
00:15:39,910 --> 00:15:47,500
So if you remember from the previous lecture, our shortest path was one from starting from one to get

154
00:15:47,500 --> 00:15:48,280
to two.

155
00:15:48,760 --> 00:15:56,950
Our shortest path was one for three and then two to get to two, and our weight of that was one plus

156
00:15:56,950 --> 00:15:58,750
one plus three.

157
00:15:58,750 --> 00:15:59,710
So five.

158
00:15:59,710 --> 00:16:02,950
So we're expecting some five to be returned here.

159
00:16:03,040 --> 00:16:10,780
So if we test this, we see that that is the value that we were indeed returned.

160
00:16:11,020 --> 00:16:15,790
So our Dijkstra's shortest path algorithm is working correctly.

161
00:16:16,780 --> 00:16:23,650
So if you have any questions about this implementation, please feel free to ask them in the Q&A section

162
00:16:23,650 --> 00:16:31,600
and in the next section, we will start looking at some algorithms that we can use when evaluating trees.