Hey there, let’s talk about paths inside of a graph. We draw a directed weighted graph and compare node-based paths to edge-based paths. Node lists alone cannot tell which edge you took when parallel edges have different costs. Edge-based paths use tuples of start, destination and weight so every route is clear.
We also cover simple paths with no repeated edges or vertices, cyclic paths that start and end on the same node, and how a cycle proves the graph is cyclic. Then we explain DAGs, directed acyclic graphs, with examples that stay acyclic and ones that gain cycles.
This sets up algorithms for later videos. Leave a comment with topics you want next. Thanks for watching and please subscribe.
00:00 Introduction to Graph Paths
00:28 Drawing a Sample Graph
02:25 What is a Path
02:42 Node-Based Paths
03:27 Adding Weights and Parallel Edges
04:34 Example Paths with Different Costs
07:19 Edge-Based Paths
07:35 Representing Paths with Tuples
11:35 Order Matters in Directed Graphs
12:52 Simple Paths
15:34 Cyclic Paths
18:22 Directed Acyclic Graphs DAGs
19:08 Building a DAG Example
21:41 Adding a Cycle to Break the DAG
23:15 Conclusion and Future Videos
=-=-=-=-=-=-=-=-=
Thanks for watching!
Find us on other social media here:
- https://www.NeuralLantern.com/social
- Twitter / X: https://x.com/NeuralLantern
- Rumble: https://rumble.com/c/c-3696939
- BitChute: https://www.bitchute.com/channel/pg1Pvv5dN4Gt
- Daily Motion: https://www.dailymotion.com/neurallantern
- Minds: https://www.minds.com/neurallantern/
- Odysee: https://odysee.com/@NeuralLantern:5
Please show your support!
- Buy me a coffee: https://ko-fi.com/neurallantern
- Subscribe + Sharing on Social Media
- Leave a comment or suggestion
- Subscribe to the Blog: https://www.NeuralLantern.com
- Watch the main “pinned” video of this channel for offers and extras
Hey there, let’s talk about paths inside of a graph.
Okay, so first thing that I’ll say is you probably should have watched my other videos already so that you understand at least the basics of graphs or maybe you already know and you just came here for a little extra.
So let’s just draw a sample graph here.
I’m going to do like random nodes.
Let’s see what am I supposed to do.
I’m supposed to like full screen that.
I’m going to draw some random nodes with some random values inside of them.
So I’m just going to do like a three here.
Maybe like a three like that.
And then I’m going to duplicate this a few times.
So I’m going to go.
This is a valid graph.
It’s just not a connected graph as we talked about in my last video.
So I’m just going to do this.
I guess that’s okay.
I’m going to change all these numbers.
Even though your graph should be able to support duplicate values in the nodes,
it’s going to be really hard to explain.
So I’m just going to change all this stuff.
9 here and then like 22.
I think that’s probably good.
So I’m going to do this.
And this.
Okay.
So still a valid graph, but there’s no chance that we could have a path anywhere in this
entire graph.
anywhere in this entire graph so that sucks we could by the way do a path
with a undirected graph but I kind of feel like I want to do direction on all
the edges so let’s see let’s do direction and also weight I’m gonna like draw an
arrow here and arrow here there I’m gonna draw edges first in a way that it
like I could find a path almost anywhere I want so I’m just going to like draw a bunch of edges
maybe like another edge over here nope that’s wrong how about this maybe another edge going up
here and an edge going up here and an edge going down there I’m just going to draw a whole bunch
of edges in the hopes that we’ll have a decent graph with lots of path possibilities okay I guess
Oh, no, no, this is not a complete graph.
I’ve just drawn a graph where you can kind of get everywhere.
Okay, so, well, I mean, what is a path?
It’s just sort of like, you know, some sort of a representation of how do you get from
one start node to some destination node, like a map.
So the first thing that we could do is we could say, let’s make a path based on nodes.
I’m going to say node-based paths.
Actually, let me get rid of this and put it on the next slide.
We’ll do this, duplicate it, that way I have the original.
Let’s pretend that our path is going to be just a list of nodes that we travel through.
So I’m going to say node-based and we’ll have one path, we’ll say path1 and then path2,
maybe we’ll do like a second path.
well at first we might think this is totally fine but uh later on it’ll get confusing in terms of
which edge did we actually take so let me show you let me show you what i mean i’m first going
to add weights to all the edges so i’m just going to do like you know four and a three over here
and then like a one and a two little one and then like a six and then like a four i’m just adding
random weights or random costs to all of the edges and um then eventually let’s see when i
let’s see when I finish doing all of that eventually we can probably realize that we
could add more than one edge going from the same start to the same destination node but give it a
different weight so that we have a little bit more of a choice so suppose for the sake of argument
that we have this six and the four here the six can go to the four at a cost of four but maybe the
a cost of one. I don’t know why it’s there. I don’t know why the four is there. Also,
we’ll just say this is our graph. So you can have edges like this that go to the same start
and destination nodes, but have different weights. So a path that is based on nodes
doesn’t really have enough information to tell us which edge we took. Let me show you what I mean.
So suppose we want to get from node, I don’t know, node three, I’ll put an S here for start.
for start. And then I guess I’ll put a D for destination or donut. I’ll put a D there on
node number 22. So we’ll say we’re going to go from node three to node 22. So start and destination
a path based, sorry, a node based path, path one, we could say maybe let’s go from the three
to the six to the four to the 12 to the nine to the 22 and that tells you all the notes that
you would hop on another path could be let’s see that first path when we went from three one six
four twelve nine uh 22 when we go from the six to the four we could have a second path here
that goes from three to one to six to four but takes a different edge this is kind of what i’m
this is kind of what i’m trying to show you notice that we have two different paths i’m going to do
one in uh maybe red so it’s going to be three one six four so from three to one and then six
and then we’ll travel along that four edge once we get to the four we’ll go 12 and then once we
Then the other path, path number two, let’s say that we chose the other edge.
We chose the six to the four edge that only cost us one.
So it would kind of look the same for the most part, except when we finally get to that
other node, we’re actually going to be going this way, right?
And then we’re going to go up and then to the right and then down.
So if you look at this carefully for a little while, maybe pause the video.
These are actually two totally different paths with two totally different costs.
different costs. So, um, you know, the cost of the orange, let me write it in orange.
It’s going to be five plus one. So six, and then a seven there, and then a eight, nine there. And
then, uh, then I guess like a 15 there and then a 16 there. So the cost of the orange pass is going
to be 16. If we switch to the red path, the only difference is the choice of edge we took between
we took between the six and the four node.
So we would increase our cost by three.
So the red path would be a cost of 19.
But how can you tell the difference in a path
that is based on a node?
It doesn’t have enough information, right?
So what we’re gonna do instead
is we’re gonna use edge-based paths.
Edge-based paths.
In some places, you know, you can use node-based paths.
That’s totally fine.
fine but for me I’m going to say let’s do edge based paths edge based paths and now we just have
to figure out how to add that extra information into the path so going from the three to the one
we’re actually traveling along an edge right we’re traveling along that five edge so let’s just stick
a tuple in there a tuple meaning just a little collection of values for those of you in c++ if
items we’re going to use three item tuples tuples not always limited to three items it could be two
three four even probably one um or much more so i’m going to say let’s use a tuple that has three
items per item or tuple and we’ll just say that we specify the start node and then the destination
node so we start at three we go to one and then the weight of the edge that we choose to travel
but we’re putting enough information into our hop
that this can be considered an edge-based path.
So when we go to the one node,
we ended on the one node, sorry, we’ve gone to the one node.
We just ended there.
So we could start on the one node for the next tuple
because then we’re going to go to the,
what are we doing first, red?
I think we’re doing red first, yeah.
We go from the one node to the six nodes.
So I’m going to go comma six.
and then we choose which edge to travel along that’s just the one edge and so 161 means start
at the one node and at the six node and take the one weighted edge then do the same thing
again for the next tuple so we’re at the six now where are we going to go we’re going to go to the
four and then we choose the edge that costs four and then for the next tuple we’re on the four
I’m going to say 12 is the destination and which edge did we choose the two even though there’s
only one choice at least we have enough information for all edges in our entire path so then again
we’re at the 12 we’re going to go to the 9 so I’m going to put a common 9 there and then we choose
to take the edge that uh what was that cost six I can’t read anymore um let me actually just look
real fast six I guess I overrode it I’m just going to assume that it’s a six um I’ve got
I guess I could erase it real fast
or move it or something
okay let’s see what is that
yeah it’s a 6 okay
so we’re on the 12 we’re going to go to the 9
and we choose to take the edge that costs 6
then we’re on the 9
and we choose to go to the 22
using the edge that costs 2
and then this last thing doesn’t need to be done
because we have the entirety of the path
in our edge based list
So I’m actually just going to copy paste this entire path and stick it into the second path
because remember the only difference between the first path and the second path that we
chose is when we were going from 6 to 4 we chose the 1 edge instead of the 4 edge.
So now look at this, I can just change that 4 to a 1 and now we definitely have two different
paths and because we’re using edges to describe our path we can tell the difference.
You know in a computer program we would know exactly which edge to travel along or even
which edge to travel along or even just a user moving their finger along a graph or whatever.
So in my opinion, edge-based paths are a little bit better.
They’re also better because if you practice writing down edge lists like this,
then you get a lot closer to a representation of a graph in your machine called an edge list.
So in an edge list, oops, I put ed light.
I don’t know why I did that.
And now the computer’s not responding.
So my mistake is immortalized.
my mistake is immortalized. Edge list representation of a graph is basically a graph is equal to
a tuple where one item in the tuple is a list of vertices and another item in the tuple
is a list of edges. So if you learn how to do edge-based paths, then you’re already a step
closer to being able to represent a graph inside of your computer program in the machine.
So another thing that I want to point out is that since this graph has direction,
the order of the start node and the destination node absolutely matters for example if we have
this three comma one here indicating we start at three and we end at one well that means there must
be an edge that points from three to one otherwise this is an invalid path if for some reason
if for some reason let me get rid of this here there’s too much stuff on the screen
three this is invalid because it’s saying that we have to start at the one node and end at the three
node but the one node has no has no edge going to the three node so this is totally invalid
does that make sense i hope it makes sense to you if this was an undirected graph where every single
edge did not have direction then the order actually wouldn’t even matter you would just
to see if an edge existed.
So let’s see, we talked about different paths.
You know, typically you would want to choose
the lowest cost path,
but there are algorithms that we can use
in future videos to compute paths.
Let’s see, something called a simple path
is where every single edge in the path is distinct.
So for example, I don’t know,
let’s say we had like a really gross path here.
Let me get rid of, let me get rid of some of this.
Let me get rid of some of this.
Get rid of the oranges maybe.
So that this is a little slightly easier to read.
Let’s see.
Did we choose?
Oh, I have to fix this.
Let’s fix the three and then the one.
And then we chose the four.
So this is the red path indeed.
So a simple path is, nope, I accidentally erased like an extra edge or something.
So I got to do one from the four to the 12.
Okay.
to the 12 okay let me just do that real fast from the 4 to the 12. at a cost of 2. okay so a simple
path is something where you don’t repeat edges so i can also write down simple path here simple path
if this was not a simple path then we would just basically have to repeat an edge somewhere
so um if any of the edges or vertices were repeated this would not be a simple path so let me just i
would not be a simple path so let me just I don’t know let me just update this real fast let’s say
we do oh what should we do let’s do I don’t know when we go from three to one to six to four
let’s go back from four to six and then we’ll take the other edge back to four and then we’ll
go up to 12 so this will be like um not a simple path if we say gosh I should have written this
this down before i drew it three to one and then one to six and then six to four and then four back
to six okay so i’m going to add another tuple so starting at four going back to six and taking
that three edge i think is what we’re looking at and then another tuple to get back when we go from
six to four and then take the um one cost edge and then once we’re at four then we can go four
cost of two and then 12 to nine at a cost of six and then nine to 22 at a cost of two okay so
i mean i’m just saying you can make a path where you just repeat a whole bunch of the edges and
nodes and you’re just like going in a circle forever like whatever you really want it’s not
necessarily going to be an efficient path or something that an algorithm should produce
but you can have a path like that maybe your character is just going crazy in the game and
because we repeat stuff on the previous slide.
Since we did not repeat anything, this is a simple path.
Okay, let’s see.
Something else that I wanna talk about is a cyclic path.
A cyclic path is basically a path
where you start and end on the same node.
Being able to find a cyclic path in a graph
is a way that you can prove that the graph is itself cyclic.
is itself cyclic. Let me try to get rid of this here. Yeah, there we go. Okay, so just
pretend for the sake of argument that I’m just kind of looking around and I’m trying to find,
you know, some path that proves I can start at the same node and end on that node without
repeating edges. So let’s see. Right, so I’m going to do take the three and go to the six.
to the six and then so i want to try if i start on the three then i want to try to find a way to get
back to the three again so i go from three to six and then i can go from six to four
and then if i go from four to six over here i’m not repeating that edge going from six to four i’m
using a new edge from four to six and then i can go from six to three again not actually repeating
means I have found a cycle in the graph. Let me just describe this path real fast in terms of
edges. So we started on three. Oops. We started on three and then we went to six and it cost us three.
And then once we were on six, we went to four. So I’m going to go from six to four. And we chose
the edge that cost us four. And then once we were on the four, we just went backwards to the six.
four going to six and we took the edge that cost three once we were on six we took the six to three
edge so six to three whoops six to three edge and that cost us three yeah did I do that right
when we go from the three to the six in the beginning I wrote down a three but I should
have written down a two hopefully you cringed on my behalf right because I was I think that red
on the left side so my brain was looking at the three but we were really taking the arrow that
points down from the three to the six so there’s a two there let me just double check one more time
six to four at cost of four four to six at cost of three six two three at cost of three
so we have started and ended uh on the same node and therefore we have found a cycle in this graph
which means this graph is cyclic what is cyclic just means it’s a graph that has a cycle
It’s a graph that has a cycle anywhere inside of it.
So this is a cyclic graph.
Make sense?
Okay, why is this important?
Well, there’s kind of like a special type of graph called a DAG,
which means a directed…
Here, let me write this down real fast.
On the next slide, so that we don’t get confused.
On the next slide, I’m going to say we have a DAG
is basically a directed…
directed, acyclic graph. What does A mean when it’s in front of something? It just means it’s
not that thing. So acyclic means not cyclic and then graph. So in some algorithms you are required
to, you know, like have a DAG before you can even use the algorithm or if you’re being tested
somewhere. So let’s just start by, you know, drawing like a little bit of a graph and we’ll
have a graph that qualifies. So I have a little graph here. If it was empty,
I don’t know if you could call it a DAG or not. I think I would because it’s empty. It could be
directed. So we have like a graph here. I would call this a DAG because it’s a graph. We don’t
have any edges, but like I could assume that this would be a directed graph. But just to make this
a better example, let’s just say we have like two nodes here. And you could also probably assume
DAG because you could assume that there are no edges in this graph but if we did add an edge
a second from now then it would be directed not the best example but so let’s just add an edge here
oh actually let’s add an edge that’s undirected real fast from from two to six and then maybe
I’ll just kind of duplicate some of these we’ll do a couple more so I can just make this more
so ask yourself is this a DAG directed acyclic well there are no cycles that I can see in the
graph there’s no paths that you can find to kind of like end where you started but this is a it is
a graph and I don’t see any cycles but it’s not directed because these edges don’t have direction
so that means right away we have to upgrade every single edge to have direction so I guess I was
going to draw a bunch more edges and now I’m just going to only draw this one edge
So this is definitely a DAG if we just sort of do it like this, maybe another edge like this,
because I don’t know about you, but I cannot find any path that allows me to start and end
on the same node. Let’s just double check it. We’ll do the two. Can we find our way back to
the two? No, because there are no incoming edges to the two. All right, that’s good. Let me just
do a check here. What about the six? If we go out to the six, from the six to the four to the
6 from the 6 to the 4 to the 11 it would have been dangerous if we could get to the 2 but we
can’t even get to the 2 so that’s fine that means the 6 is okay we cannot find our way back there
the 4 we can go to the 11 but we can’t go any further we’re at a dead end we can’t even go to
the 6 that means the 4 can’t find its way back to itself where you can’t find a path that goes back
the 11 has only incoming edges so that’s automatically you know a dead end so all of
nodes qualify as we could not start and also end at that node with a single path so that’s good
that means this is a DAG a directed acyclic graph if you want to make this into not a DAG just figure
out how to add a path so that you end up with a cycle so what was the first thing we did the 2
goes to the 6 goes to the 4 goes to 11 then it’s a dead end we could either add an edge from 11 to 2
to make a cycle but that’s a little bit too easy right because if you see any pair of nodes
right because if you see any pair of nodes with arrows kind of pointing back and forth between the
two nodes then right away that alone is a cycle so I’m just going to maybe do an arrow or an edge
pointing from four to two then it doesn’t look so much like a cycle although it’s not too hard
to realize that there is a cycle in this graph in this graph so this is not a DAG let me show you
and then from four to two.
And therefore we would have a cycle.
So this whole graph is not considered acyclic.
This graph has a cycle.
And if we want to do an edge-based path,
we don’t have weights on this graph right now.
So we could describe the path as such.
We could say, start at two, go to six.
And if your edge list is of a graph
that doesn’t even have weight at all,
then you don’t really need that third item in the tuple.
item in the tuple you can just do a start node and a destination node this does kind of preclude
you from having parallel edges you know two different edges that point from the same start
node to the same end node so as i go from two to six and then from six to uh four and then from
four to two and then we have a cycle and that’s it okay i think this is all i really wanted to
talk about for this particular video in future videos we’re going to do algorithms and then
some others up already that have graph properties and connectedness and definitions and things like
that. So leave a comment asking about some algorithm or some property of a graph that
you might be interested in. Otherwise, thank you so much for watching this video. I hope you learned
a little bit of stuff. And I hope you had a little bit of fun. I’ll see you in the next video.
Yeah, I’m gonna go eat some cookies. No, I shouldn’t do that. But I’m still going to.
Hey everybody, thanks for watching this video again from the bottom of my heart.
I really appreciate it.
I do hope you did learn something and have some fun.
If you could do me a please, a small little favor, could you please subscribe and follow
this channel or these videos or whatever it is you do on the current social media website
that you’re looking at right now.
It would really mean the world to me and it’ll help make more videos and grow this community.
So we’ll be able to do more videos, longer videos, better videos, or just I’ll be able
better videos or just I’ll be able to keep making videos in general so please
do do me a kindness and and subscribe you know sometimes I’m sleeping in the
middle of the night and I just wake up because I know somebody subscribed or
followed it just wakes me up and I get filled with joy that’s exactly what
happens every single time so you could do it as a nice favor to me or you could
you control me if you want to just wake me up in the middle of the night just
subscribe and then I’ll just wake up I promise that’s what will happen also if
if you look at the middle of the screen right now you should see a qr code which you can scan
in order to go to the website which i think is also named somewhere at the bottom of this video
and it’ll take you to my main website where you can just kind of like see all the videos i
published and the services and tutorials and things that i offer and all that good stuff and
if you have a suggestion for uh clarifications or errata or just future videos that you want to see
Or if you just want to say, hey, what’s up?
What’s going on?
You know, just send me a comment, whatever.
I also wake up for those in the middle of the night.
I get, I wake up in a cold sweat and I’m like,
it would really, it really mean the world to me.
I would really appreciate it.
So again, thank you so much for watching this video
and enjoy the cool music as I fade into the darkness,
which is coming for us all.
so
Thank you.
I’m going to go ahead and get started.
Thank you.
