Who doesn't like graph theory? Come on... it is the foundation of all living beings! Ok maybe not but it is still a bit interesting from a theoretical standpoint. Graph theory is the study of graphs and their relationships between points on that graph and their overall collection. It is often made up of vertexes (aka nodes) and the connections between them known as edges. Linked together they form a spider web and using Dijkstra's algorithm we can find the shortest distance between our start node and the end node. I will show you how using C++ on this entry of the Programmer's Underground!
<Metallica's Enter Sandman meets their arch nemesis...Sleepy from snow white theme music>
So how does it all work? Graph theory can get pretty complicated and studying the relationship between nodes using their edges isn't exactly something we dream about. Unless you are part of DIC staff and addicted to programming theory. Hopefully I can put that nightmare to rest with a little explanation of Dijkstra's Algorithm and how it works for finding the path with the "least cost" between two nodes of a graph.
But first I want to show you a classic example of a graph we are talking about here and what Dijkstra's Algorithm was designed to do.
The above graph I got from Wikipedia. It is a very simple graph but it will illustrate our point nicely. Assume for a moment we are at node 6 and we want to find the shortest path to node 2. Typically we would add up the distance between nodes 6, 4, 3 and 2 and see if that is shorter than going 6, 4, 5, 2 or 6, 4, 5, 1, 2. With a small graph like this with limited paths it is easy to look at the graph and know quickly which is the shortest path. However, what if the graph had as many as 3 more points and exponentially bigger path options? There will be a point where you can no longer do all the summaries in your head let alone find all options to get to a node to compare them for the shortest distance.
This is where Dijkstra's Algorithm comes into play. It starts out at node 6 and runs through all the neighboring nodes and determines which is shorter using a "greedy" mechanism. It goes for the least cost (the shortest path to get one more node closer to the destination). In our example node 6 has only one path, to node 4 so that is a given. But the algorithm then comes to play with node 4. Is it shorter to go to node 3 or node 5. Lets say it is shorter to go to node 5. So the algorithm takes that route.
It then again validates neighboring nodes that have NOT been visited already. Since node 4 has been visited, we don't consider it an option. We instead check out nodes 2 and 1. But in addition to these paths, we keep track of the path back from 4 to 3. If the path from 4 5 to 1 is getting expensive, it might be worth going back from 4 to node 3 and try that route instead. Either way the algorithm will not stop until all nodes have been visited and thus all paths have been run, yielding the shortest path to our destination and having a side effect of showing us the shortest paths to all nodes. So instead of just finding our one destination to node 2, once the algorithm has been ran we will know the shortest paths to nodes 4, 5, 1, 3 etc.
So lets take a look at how this works in C++....
The in code comments explain the process step by step. As you can see we setup a table of distances between various nodes in a graph which has 8 vertexes or nodes and 10 paths between these nodes. Start at node A which is at L[0][0] we are attempting to find the distances to all points for the shortest routes.
Just because we evaluate all routes it doesn't mean that all routes will be used in the calculation of the shortest path to a specific node. In this case we do use all paths when reaching all nodes. As you can see from the code, I mark the list of total nodes as levels and move through them continuously as I evaluate minimum paths (Dist array). The value minValue is actually the minimum distance between two nodes. We use the original multidimensional array to currently store our accumulations between the nodes.
The result of this program is two lists of integers. The first list represents the distances between our start node and the nodes to other points. The second list represents which nodes are available (aka unvisited). By the end of the iterations through the levels, you will see that all points have become visited (all show -1) and thus we know we are done evaluating all paths.
The idea is a bit complex to get your head around, so take your time and read through the steps. This particular algorithm is great for video game design given that your character could reach a destination through a different series of paths... be it in a cave, or maze or whatever. Great for monsters who need to also find the optimal path to reach your character to kill it.
Hope you like it and enjoy! Thanks for reading. :)
If you want more blog entries like this, check out the official blog over on The Coders Lexicon. There you will find more code, more guides and more resources for programmers of all skill levels!
<Metallica's Enter Sandman meets their arch nemesis...Sleepy from snow white theme music>
So how does it all work? Graph theory can get pretty complicated and studying the relationship between nodes using their edges isn't exactly something we dream about. Unless you are part of DIC staff and addicted to programming theory. Hopefully I can put that nightmare to rest with a little explanation of Dijkstra's Algorithm and how it works for finding the path with the "least cost" between two nodes of a graph.
But first I want to show you a classic example of a graph we are talking about here and what Dijkstra's Algorithm was designed to do.
The above graph I got from Wikipedia. It is a very simple graph but it will illustrate our point nicely. Assume for a moment we are at node 6 and we want to find the shortest path to node 2. Typically we would add up the distance between nodes 6, 4, 3 and 2 and see if that is shorter than going 6, 4, 5, 2 or 6, 4, 5, 1, 2. With a small graph like this with limited paths it is easy to look at the graph and know quickly which is the shortest path. However, what if the graph had as many as 3 more points and exponentially bigger path options? There will be a point where you can no longer do all the summaries in your head let alone find all options to get to a node to compare them for the shortest distance.
This is where Dijkstra's Algorithm comes into play. It starts out at node 6 and runs through all the neighboring nodes and determines which is shorter using a "greedy" mechanism. It goes for the least cost (the shortest path to get one more node closer to the destination). In our example node 6 has only one path, to node 4 so that is a given. But the algorithm then comes to play with node 4. Is it shorter to go to node 3 or node 5. Lets say it is shorter to go to node 5. So the algorithm takes that route.
It then again validates neighboring nodes that have NOT been visited already. Since node 4 has been visited, we don't consider it an option. We instead check out nodes 2 and 1. But in addition to these paths, we keep track of the path back from 4 to 3. If the path from 4 5 to 1 is getting expensive, it might be worth going back from 4 to node 3 and try that route instead. Either way the algorithm will not stop until all nodes have been visited and thus all paths have been run, yielding the shortest path to our destination and having a side effect of showing us the shortest paths to all nodes. So instead of just finding our one destination to node 2, once the algorithm has been ran we will know the shortest paths to nodes 4, 5, 1, 3 etc.
So lets take a look at how this works in C++....
// Dijkstra's Algorithm // Written to C++ by Martyr2 // Dream In Code #include <iostream> using namespace std; // Define the levels of the graph const int LEVELS = 8; // Prototype for our Dijkstra function void Dijkstra(int *, int *, int[LEVELS][LEVELS]); int main() { // Define a multidimensional array of lengths between points // Those designated -1 means no path exists beween those two points. // Think of this as a numeric table showing relationships. int L[LEVELS][LEVELS] = { {-1, 5, -1, -1, -1, 3, -1, -1}, { 5, -1, 2, -1, -1, -1, 3, -1}, {-1, 2, -1, 6, -1, -1, -1, 10}, {-1, -1, 6, -1, 3, -1, -1, -1}, {-1, -1, -1, 3, -1, 8, -1, 5}, { 3, -1, -1, -1, 8, -1, 7, -1}, {-1, 3, -1, -1, -1, 7, -1, 2}, {-1, -1, 10, -1, 5, -1, 2, -1} }; // An array to hold vertexes and full path distances int Vertexes[LEVELS]; int Dist[LEVELS]; // First we just set our vertexes to a count up to the number of // levels. Here we label vertexes 0 through 7 (thus 8 levels) for (int i = 0; i < LEVELS; i++) { Vertexes[i] = i; } // Our first vertex is a starting vertex, so set it to one // and its distance will be 0. Vertexes[0] = -1; Dist[0] = 0; // Set the distances according to our levels array defined above. // Dist array keeps track of the legs and adds to them as we move through // paths of the graph for (int i = 1; i < LEVELS; i++) { Dist[i] = L[0][i]; } // Ok, lets start at level 1 and move to level 7 // Each time we call our function to evaluate the following... // 1. What paths are available to us (we use the vertexes closes to our point) // 2. How far are they away? // 3. Take whichever is shortest path with the least cost. for (int curlevel = 1; curlevel < LEVELS; curlevel++) { Dijkstra(Vertexes, Dist, L); cout << "Level " << curlevel << endl; // Just to show what the current distances are for each path as we // loop through the vertexs and evaluate. for (int i = 0; i < LEVELS; i++) { cout << Dist[i] << " "; } cout << endl; // Show which vertexs have yet to be visted (-1 means visited) for (int i = 0; i < LEVELS; i++) { cout << Vertexes[i] << " "; } cout << endl; } return 0; } // Dijkstra implements the algorithm for checking the vertexs and their // relative path distances in relation to where we are in the graph. void Dijkstra(int *Vertexes, int *Dist, int L[LEVELS][LEVELS]) { int minValue = 32767; int minNode = 0; // Loop through the vertexs to see if they have been visited // If they haven't, check their distance and see if it is smaller than // our current shortest distance. If so, set the new shortest distance // to minValue and label the node as the shortest for (int i = 0; i < LEVELS; i++) { if (Vertexes[i] == -1) { continue; } if (Dist[i] > 0 && Dist[i] < minValue) { minValue = Dist[i]; minNode = i; } } // Mark the new shortest distance vertex as visited Vertexes[minNode] = -1; // Add the distance to the overall path distance from start // to destination. The result is a list of values at the end which will // show the shortest paths between any two nodes. for (int i = 0; i < LEVELS; i++) { if (L[minNode][i] < 0) { continue; } if (Dist[i] < 0) { Dist[i] = minValue + L[minNode][i]; continue; } if ((Dist[minNode] + L[minNode][i]) < Dist[i]) { Dist[i] = minValue + L[minNode][i]; } } }
The in code comments explain the process step by step. As you can see we setup a table of distances between various nodes in a graph which has 8 vertexes or nodes and 10 paths between these nodes. Start at node A which is at L[0][0] we are attempting to find the distances to all points for the shortest routes.
Just because we evaluate all routes it doesn't mean that all routes will be used in the calculation of the shortest path to a specific node. In this case we do use all paths when reaching all nodes. As you can see from the code, I mark the list of total nodes as levels and move through them continuously as I evaluate minimum paths (Dist array). The value minValue is actually the minimum distance between two nodes. We use the original multidimensional array to currently store our accumulations between the nodes.
The result of this program is two lists of integers. The first list represents the distances between our start node and the nodes to other points. The second list represents which nodes are available (aka unvisited). By the end of the iterations through the levels, you will see that all points have become visited (all show -1) and thus we know we are done evaluating all paths.
The idea is a bit complex to get your head around, so take your time and read through the steps. This particular algorithm is great for video game design given that your character could reach a destination through a different series of paths... be it in a cave, or maze or whatever. Great for monsters who need to also find the optimal path to reach your character to kill it.
Hope you like it and enjoy! Thanks for reading. :)
If you want more blog entries like this, check out the official blog over on The Coders Lexicon. There you will find more code, more guides and more resources for programmers of all skill levels!
3 Comments On This Entry
Page 1 of 1
ksyme99
23 February 2009 - 04:53 AM
This is great, thanks! Works nicely and is written in such a way I can actually see the algorithim working. I was wondering though, how do you change the starting node, if possible? It would be useful to do this for each node, hence working out the shortest paths between all nodes and all other nodes. I am still going through it, so may figure it out yet, but wondering if there is something simple i am missing.
ksyme99
23 February 2009 - 05:17 AM
I think I worked it out - just put another for loop round the stuff in main, not the declerations. Looped this from 0 to LEVELS and changed the couple of loops to use this value instead.
Also needed to set the Dist vector at the start of each loop - I set all values in Dist to -1.
After changing the output to only give the final Dist for each starting node, this now gives a matrix of the shortest paths between all nodes and all other nodes (I think...have checked using some examples I ahve done by hand, it seems to work!).
Thanks very much for this code - will help a lot!
// Our first vertex is a starting vertex, so set it to one // and its distance will be 0. Vertexes[k] = -1; Dist[k] = 0; // Set the distances according to our levels array defined above. // Dist array keeps track of the legs and adds to them as we move through // paths of the graph for (int i = 0; i < LEVELS; i++) { if(i!=k) Dist[i] = L[k][i]; }
Also needed to set the Dist vector at the start of each loop - I set all values in Dist to -1.
After changing the output to only give the final Dist for each starting node, this now gives a matrix of the shortest paths between all nodes and all other nodes (I think...have checked using some examples I ahve done by hand, it seems to work!).
Thanks very much for this code - will help a lot!
gm1
11 September 2009 - 06:03 AM
I am trying to use the algorithm submitted by Martyr but I converted it to VB. NET as that's currently using. I populated the 2 arrays the Vertices and Distances with the nodes I have in datatable and their distances. I also have a start and a destination node known, so I just need what paths I will be traversing. However the levels thing is getting problematic, I don't know how it will feature in my table!
Public Class Route
' Define the levels of the graph
Private Const LEVELS As Integer = 100
' Dijkstra implements the algorithm for checking the vertexs and their
' relative path distances in relation to where we are in the graph.
' Prototype for our Dijkstra function
Private Sub Dijkstra(ByVal Vertexes() As Integer, ByVal Dist() As Integer, ByVal L(,) As Integer)
Dim minValue As Integer = 32767
Dim minNode As Integer = 0
' Loop through the vertexs to see if they have been visited
' If they haven't, check their distance and see if it is smaller than
' our current shortest distance. If so, set the new shortest distance
' to minValue and label the node as the shortest
For i As Integer = 0 To LEVELS - 1
If Vertexes(i) = -1 Then
Continue For
End If
If Dist(i) > 0 AndAlso Dist(i) < minValue Then
minValue = Dist(i)
minNode = i
End If
Next i
' Mark the new shortest distance vertex as visited
Vertexes(minNode) = -1
' Add the distance to the overall path distance from start
' to destination. The result is a list of values at the end which will
' show the shortest paths between any two nodes.
For i As Integer = 0 To LEVELS - 1
If L(minNode, i) < 0 Then
Continue For
End If
If Dist(i) < 0 Then
Dist(i) = minValue + L(minNode, i)
Continue For
End If
If (Dist(minNode) + L(minNode, i)) < Dist(i) Then
Dist(i) = minValue + L(minNode, i)
End If
Next i
End Sub
Private Shared Function Main() As Integer
' Define a multidimensional array of lengths between points
' Those designated -1 means no path exists beween those two points.
' Think of this as a numeric table showing relationships.
Dim tblNodes As DataTable
Dim dstNodes As DataSet
Dim tblDistance As DataTable
Dim dstDistance As DataSet
Dim strSQL As String = "Select FromNode,ToNode,Link_ID From LLNODES_AREA"
Dim thisSqlDataAdapter As New SqlDataAdapter(strSQL, strConnection)
tblNodes = New DataTable
dstNodes = New DataSet
thisSqlDataAdapter.Fill(dstNodes)
tblNodes = dstNodes.Tables(0)
Dim intNumOfNodes As Integer
'Dim aryReturn() As StreetNodes
intNumOfNodes = tblNodes.Rows.Count
Dim strDistanceSQL As String = "Select Distance,Link_ID From LLNODES_AREA"
Dim saDist As New SqlDataAdapter(strSQL, strConnection)
tblDistance = New DataTable
dstDistance = New DataSet
thisSqlDataAdapter.Fill(dstDistance)
tblDistance = dstDistance.Tables(0)
Dim intDist As Integer
'Dim aryReturn() As StreetNodes
intDist = tblDistance.Rows.Count
'if no records set intNumRows to 1 for following line
''stop runtime error of declaring a negative length array
StartNode = 22042
DestinationNode = 53268
Dim L(,) As Integer = {{-1, 5, -1, -1, -1, 3, -1, -1}, {5, -1, 2, -1, -1, -1, 3, -1}, {-1, 2, -1, 6, -1, -1, -1, 10}, {-1, -1, 6, -1, 3, -1, -1, -1}, {-1, -1, -1, 3, -1, 8, -1, 5}, {3, -1, -1, -1, 8, -1, 7, -1}, {-1, 3, -1, -1, -1, 7, -1, 2}, {-1, -1, 10, -1, 5, -1, 2, -1}}
' An array to hold vertexes and full path distances
Dim Vertexes(intNumOfNodes - 1) As Integer
Dim Dist(intDist - 1) As Integer
' First we just set our vertexes to a count up to the number of
' levels. Here we label vertexes 0 through 7 (thus 8 levels)
For i As Integer = 0 To LEVELS - 1
Vertexes(i) = i
Next i
' Our first vertex is a starting vertex, so set it to one
' and its distance will be 0.
Vertexes(0) = -1
Dist(0) = 0
' Set the distances according to our levels array defined above.
' Dist array keeps track of the legs and adds to them as we move through
' paths of the graph
For i As Integer = 1 To LEVELS - 1
Dist(i) = L(0, i)
Next i
' Ok, lets start at level 1 and move to level 7
' Each time we call our function to evaluate the following...
' 1. What paths are available to us (we use the vertexes closes to our point)
' 2. How far are they away?
' 3. Take whichever is shortest path with the least cost.
For curlevel As Integer = 1 To LEVELS - 1
'Dijkstra(Vertexes, Dist, L)
Console.Write("Level ")
Console.Write(curlevel)
Console.Write(ControlChars.Lf)
' Just to show what the current distances are for each path as we
' loop through the vertexs and evaluate.
For i As Integer = 0 To LEVELS - 1
Console.Write(Dist(i))
Console.Write(" ")
Next i
Console.Write(ControlChars.Lf)
' Show which vertexs have yet to be visted (-1 means visited)
For i As Integer = 0 To LEVELS - 1
Console.Write(Vertexes(i))
Console.Write(" ")
Next i
Console.Write(ControlChars.Lf)
Next curlevel
Return 0
End Function
Any help would be greatly appreciated!!!
Public Class Route
' Define the levels of the graph
Private Const LEVELS As Integer = 100
' Dijkstra implements the algorithm for checking the vertexs and their
' relative path distances in relation to where we are in the graph.
' Prototype for our Dijkstra function
Private Sub Dijkstra(ByVal Vertexes() As Integer, ByVal Dist() As Integer, ByVal L(,) As Integer)
Dim minValue As Integer = 32767
Dim minNode As Integer = 0
' Loop through the vertexs to see if they have been visited
' If they haven't, check their distance and see if it is smaller than
' our current shortest distance. If so, set the new shortest distance
' to minValue and label the node as the shortest
For i As Integer = 0 To LEVELS - 1
If Vertexes(i) = -1 Then
Continue For
End If
If Dist(i) > 0 AndAlso Dist(i) < minValue Then
minValue = Dist(i)
minNode = i
End If
Next i
' Mark the new shortest distance vertex as visited
Vertexes(minNode) = -1
' Add the distance to the overall path distance from start
' to destination. The result is a list of values at the end which will
' show the shortest paths between any two nodes.
For i As Integer = 0 To LEVELS - 1
If L(minNode, i) < 0 Then
Continue For
End If
If Dist(i) < 0 Then
Dist(i) = minValue + L(minNode, i)
Continue For
End If
If (Dist(minNode) + L(minNode, i)) < Dist(i) Then
Dist(i) = minValue + L(minNode, i)
End If
Next i
End Sub
Private Shared Function Main() As Integer
' Define a multidimensional array of lengths between points
' Those designated -1 means no path exists beween those two points.
' Think of this as a numeric table showing relationships.
Dim tblNodes As DataTable
Dim dstNodes As DataSet
Dim tblDistance As DataTable
Dim dstDistance As DataSet
Dim strSQL As String = "Select FromNode,ToNode,Link_ID From LLNODES_AREA"
Dim thisSqlDataAdapter As New SqlDataAdapter(strSQL, strConnection)
tblNodes = New DataTable
dstNodes = New DataSet
thisSqlDataAdapter.Fill(dstNodes)
tblNodes = dstNodes.Tables(0)
Dim intNumOfNodes As Integer
'Dim aryReturn() As StreetNodes
intNumOfNodes = tblNodes.Rows.Count
Dim strDistanceSQL As String = "Select Distance,Link_ID From LLNODES_AREA"
Dim saDist As New SqlDataAdapter(strSQL, strConnection)
tblDistance = New DataTable
dstDistance = New DataSet
thisSqlDataAdapter.Fill(dstDistance)
tblDistance = dstDistance.Tables(0)
Dim intDist As Integer
'Dim aryReturn() As StreetNodes
intDist = tblDistance.Rows.Count
'if no records set intNumRows to 1 for following line
''stop runtime error of declaring a negative length array
StartNode = 22042
DestinationNode = 53268
Dim L(,) As Integer = {{-1, 5, -1, -1, -1, 3, -1, -1}, {5, -1, 2, -1, -1, -1, 3, -1}, {-1, 2, -1, 6, -1, -1, -1, 10}, {-1, -1, 6, -1, 3, -1, -1, -1}, {-1, -1, -1, 3, -1, 8, -1, 5}, {3, -1, -1, -1, 8, -1, 7, -1}, {-1, 3, -1, -1, -1, 7, -1, 2}, {-1, -1, 10, -1, 5, -1, 2, -1}}
' An array to hold vertexes and full path distances
Dim Vertexes(intNumOfNodes - 1) As Integer
Dim Dist(intDist - 1) As Integer
' First we just set our vertexes to a count up to the number of
' levels. Here we label vertexes 0 through 7 (thus 8 levels)
For i As Integer = 0 To LEVELS - 1
Vertexes(i) = i
Next i
' Our first vertex is a starting vertex, so set it to one
' and its distance will be 0.
Vertexes(0) = -1
Dist(0) = 0
' Set the distances according to our levels array defined above.
' Dist array keeps track of the legs and adds to them as we move through
' paths of the graph
For i As Integer = 1 To LEVELS - 1
Dist(i) = L(0, i)
Next i
' Ok, lets start at level 1 and move to level 7
' Each time we call our function to evaluate the following...
' 1. What paths are available to us (we use the vertexes closes to our point)
' 2. How far are they away?
' 3. Take whichever is shortest path with the least cost.
For curlevel As Integer = 1 To LEVELS - 1
'Dijkstra(Vertexes, Dist, L)
Console.Write("Level ")
Console.Write(curlevel)
Console.Write(ControlChars.Lf)
' Just to show what the current distances are for each path as we
' loop through the vertexs and evaluate.
For i As Integer = 0 To LEVELS - 1
Console.Write(Dist(i))
Console.Write(" ")
Next i
Console.Write(ControlChars.Lf)
' Show which vertexs have yet to be visted (-1 means visited)
For i As Integer = 0 To LEVELS - 1
Console.Write(Vertexes(i))
Console.Write(" ")
Next i
Console.Write(ControlChars.Lf)
Next curlevel
Return 0
End Function
Any help would be greatly appreciated!!!
Page 1 of 1
← January 2021 →
S | M | T | W | T | F | S |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
31 |
Tags
- announcement
- APIs
- Basics
- Best Practices
- BLOB
- Book Reviews
- Bots
- C#
- CSS
- Deep Underground
- Deep Underground (misc)
- design
- desktop programming
- Drawing
- Forms
- Games
- General Discussion
- Hack the Planet!! (Just for fun category)
- HTML
- images
- Interviews
- Java
- JavaScript
- jquery
- menus
- PHP
- Python
- Ruby
- Search theory
- Security
- Theory
- Tips and Tricks
- VB.NET
- Web API
- web development
My Blog Links
Recent Entries
Recent Comments
Search My Blog
0 user(s) viewing
0 Guests
0 member(s)
0 anonymous member(s)
0 member(s)
0 anonymous member(s)