Graph Traversal Algorithms

Dr Ian Cornelius

Hello

Hello (1)

Learning Outcomes

Understand the concept of different algorithms for traversing a graph
Implement and use a graph traversing algorithm in their bodies of work

Graph Traversal

Graph Traversal (1)

Traversing a Graph

Storing data within a graph is fairly easy
However, they are not useful until you can search for data or find information about the interconnections
Algorithms that interrogate the graph by following the edges are known as traversal algorithms

In the previous lecture we discussed how graphs can be used to store data, which is fairly easy. Although when it comes to using graphs, it usually means traversing through them to extract the data. Travelling through the graph and using the structure of it can be useful to get information. Algorithms that interrogate a graph by following edges are known as traversal algorithms.

We looked at a few of these traversal algorithms earlier, known as pre-, post- and in-order traversal. However, in this lecture we shall look at some others in more detail. More information on the algorithms we shall be looking at will come later on in this lecture.

Graph Traversal (2)

Principles for Traversing a Graph

Start from a root node
- this may be specific to the problem
  - i.e. the starting address in a route planner
- or it could be the \(0^{th}\) node in the graph
- or it may be something intelligently selected based on the search parameters
  - i.e. looking for restaurants near-by in a graph consisting of points of interest, and there is a starting node that is specific to restaurant searches
There is a goal node
- this may be the address you are trying to navigate to in the route planner
- it may be parameters defining a goal node or a set of goal nodes
  - i.e. a list of universities at least 200 miles away from my parents’ house
The graph is traversed from node to node, along the edges that connect them
- this is done until the goal is reached
- or a satisfactory node has met the parameters
- or a large set of nodes which meet the parameters are found

The general principle of traversing a graph is that we have what we call a root node, or a starting point, and unlike a tree, this could be at a point anywhere in our graph.

The method in which you will traverse a graph could be specific to the problem that you are trying to solve. For example, the root node may be the first node in the graph, it could be at the centre point, or it could also be something intelligently selected based upon a given set of search parameters. For example, if we were searching for restaurants, then we would look for points of interest and start from a particular place, i.e. Wagamama in the city centre and move on from there.

There is also generally a goal node, and this is something that we might be looking for. This could be the address in the map, or we may have some other parameters that define what the goal is. For example, a restaurant that is no further than half-a-mile. Alternatively, instead of a single node, it may be something that first meets the criteria we set.

We can traverse a graph as if we are moving our attention through it by point to point. We do this by following the edges until we reach the goal, which is the satisfactory node that meets our parameters. Alternatively, we may find we have gone through them all and nothing comes back, as such, we have finished our journey but with no restaurant to go to.

Graph Traversal (3)

Approaches for Traversing a Graph

There are various approaches to solving this problem of traversing a graph
- however, there is no best method of doing this
The nature of the data you are after matters when choosing a graph traversal algorithm
The structure of the graph also matters
The desired output also matters
- this could be a single specific node
- the first node that meets a set of parameters
- several nodes that meet the set of parameters

When it comes to traversing a node, you will not be surprised to know there are lots of different ways to do it. Each one of these potential ways to traverse a graph is useful for different situations. This could be the kind of data that is being stored in the graph, or the kind of information we want to extract out of it.

The structure of the graph also plays an important part in how we would traverse a graph. This would be based upon the type of graph that is being used, i.e. directed, undirected, etc.

The desired output could be a single specific node, the first node that meets a given criteria, or it could also depend on the type of traversal algorithm that is used.

Graph Traversal Algorithms

Graph Traversal Algorithms (1)

Depth-First Search (DFS)

Standard DFS implementation will put each vertex of the graph into one of two categories:
1. Visited
2. Unvisited
The algorithm will mark each vertex as visited whilst avoiding cycles
The algorithm consists of the following steps:
1. Add any of the graph vertices on top of a stack
2. Take the top item of the stack and add it to the visited list
3. Create a list of the adjacent vertices for that node
  - add any that are not in the visited list to the top of the stack
4. Keep repeat steps 2 and 3 until the stack is empty

The first algorithm we shall look at is the depth-first search. The algorithm traverses the entire graph and will mark each vertex as visited whilst avoiding any cycles that may occur in the graph. Whenever a vertex is visited in our search, the algorithm will visit all the vertices of any unvisited neighbours. All the edges that can be visited from that node will be added to a stack, often known as an unvisited list. The next vertex to be visited is then determined by selecting the first item in the unvisited list and following the edge that leads to that node, and continue following the branches through until the end of the graph is reached, i.e. there are no more nodes left to visit.

The algorithm works by following these steps:

Add any of the graph vertices onto the top of the stack
We then take the top item off the stack and add it to the visited list
We then create a list of adjacent vertices for that node and add any that are not in the visited list to the top of the stack
We keep repeating steps 2 and 3 until our stack is empty

Graph Traversal Algorithms (2)

DFS on an Undirected Graph

Click Start to proceed!

Unvisited

Visited

Lets walk-through the depth-first search algorithm together on an undirected graph. On the right-hand-side of the screen, you can see that we have the graph that we wish to move through. We also have two stacks, one for the unvisited nodes, and the other for visited nodes. To begin our search, I am going to click the start button.

Click Start

We begin our journey by selecting a root node, and this is the node that we shall begin our journey from. In this case, I have decided to begin at node A. Immediately, we can begin populating our stacks on the right-hand-side of the screen. Therefore, you can see that because we have started at node A we classify this node as visited.

We then need to observe the nodes that are connected to the node we are visiting. We therefore, explore the edges, and we can see that the nodes B, C and D are connected and these nodes are added to our unvisited stack.

To progress, we pick the node at the top (or head as it is also known) of our unvisited stack, and proceed to visit the node.

Click Next

The next node we arrive at is node B and we add this node to our visited stack. We can now begin repeating the process from earlier, whereby we check whether there are any unvisited nodes, and we add these to our stack. In this case, we can see that nodes A and C are connected to node B. However, as we have already visited node A we can disregard adding this to our unvisited stack, and as node C is already in our stack, we do not need to add this node either.

To progress, we pick the node at the top of our unvisited stack, and proceed to visit the node.

Click Next

The next node we arrive at is node C and we add this node to our visited stack. Once again, we begin the process of checking the unvisited nodes that are connected to this node. In this instance, we can see that there is a new node to add to our unvisited stack, node E. These new nodes are added to the top of our unvisited stack.

To progress, we pick the node at the top of our unvisited stack, and proceed to visit the node.

Click Next

The next node we arrive at is node E and we add this node to our visited stack. By now, you should be familiar with the process that we’re following. However, for those of you who are not, we check whether there are any unvisited nodes that are attached to the current node we are visiting.

In this case, the only attached node is node C, and as we have previously visited this node, we can ignore it and not add it to our stack. To progress, we pick the node at the top of our unvisited stack, and proceed to visit the node.

Click Next

The next node we arrive at is node C and we add this node to our visited stack. We can observe from this node, that the only connection is node A and as this node has previously been visited, we do not need to add this to our unvisited stack. As such, our unvisited stack is now empty, and we have completed our journey.

Click Next

Some key takeaways from this method of traversal, is that each node is visited to how it’s been populated in the unvisited stack. When you visit a node, and it needs to be added to the unvisited stack, it will be populated at the head of the stack. The journey is continued until there are no more nodes left in the unvisited stack.

Graph Traversal Algorithms (3)

DFS on a Directed Graph

Click Start to proceed!

Unvisited

Visited

Lets walk-through the depth-first search algorithm together on a directed graph. On the right-hand-side of the screen, you can see that we have the graph that we wish to move through. We also have two stacks, one for the unvisited nodes, and the other for visited nodes. To begin our search, I am going to click the start button.

Click Start

We then need to observe the nodes that are connected to the node we are visiting. We therefore, explore the edges that we can follow, and remember, this is a directed graph, and we can see that the nodes E, and G are connected and these nodes are added to our unvisited stack.

To progress, we pick the node at the top (or head as it is also known) of our unvisited stack, and proceed to visit the node.

Click Next

The next node we arrive at is node E and we add this node to our visited stack. The same process as the undirected graph applies, and from our currently visited node, we need to check whether there are any unvisited nodes and at these at the top of the unvisited node stack.

In this case, we can see that node H is the only connected node from node E and we therefore at this node to the top of our unvisited stack.

To progress, we pick the node at the top of our unvisited stack, and proceed to visit the node.

Click Next

The next node we arrive at is node H and we add this node to our visited stack. From this node, we check whether there are any unvisited nodes that need to be added to our unvisited stack. In this case, there is a node, and we add node F to the top of our unvisited stack.

To progress, we pick the node at the top of our unvisited stack, and proceed to visit the node.

Click Next

The next node we arrive at is node F and we add this node to our visited stack. From this node, we check whether there are any unvisited nodes that need to be added to our unvisited stack. In this case, there is a node, and we add node D to the top of our unvisited stack.

To progress, we pick the node at the top of our unvisited stack, and proceed to visit the node.

Click Next

The next node we arrive at is node D and we add this node to our visited stack. From this node, we check whether there are any unvisited nodes that need to be added to our unvisited stack. In this case, there is a node, and we add node C to the top of our unvisited stack.

To progress, we pick the node at the top of our unvisited stack, and proceed to visit the node.

Click Next

The next node we arrive at is node C and we add this node to our visited stack. From this node, we check whether there are any unvisited nodes that need to be added to our unvisited stack. In this case, there is only a single node that is connected, and we have previously visited this node, and as such we do not need to add this to our unvisited stack.

Instead, we proceed to move to node A as we need to follow the direction of our graph, and we still have an unvisited node in our list.

Click Next

The next node we arrive at is node A, and as we have already previously visited this node, we do not need to add it to our visited stack. From this node, we observe whether there are any other nodes that we need to visit that are not already in our stack.

In this case, the only node we need to visit is node G and this is already in our stack. Therefore, we do not need to add this node to our unvisited stack again. To progress, we pick the node at the top of our unvisited stack, and proceed to visit the node.

Click Next

The next node we arrive at is node G and we add this node to our visited stack. From our current node, we need to check whether we can visit any other node. In this instance, there are no further nodes that have an outgoing connection from this node. However, there is another node, and that is node B which has an incoming connection to node G. Therefore, we need to add this node to our unvisited stack.

Click Next

As we are unable to traverse to node B, it stays in our unvisited stack, and we have now reached the end of our algorithm journey. Some key takeaways from this method are the same as before, but with some added directionality. We must always follow the direction the edge is pointing.

If this were to be an undirected graph, we could have traversed to node B either from node G or from node A. However, as the graph is directed, and the node has only outgoing connections and none incoming, we are unable to mark the node as visited.

Graph Traversal Algorithms (4)

Time Complexity of DFS

The time complexity of DFS is represented in the form \(O(V + E)\), where
- \(V\) is the number of nodes
- \(E\) is the number of edges
The space complexity of DFS is \(O(V)\), where \(V\) is the number of nodes
DFS is useful in the following applications:
- detecting a cycle in a graph
- topological sorting
- finding strongly connected components of a graph
- path finding

The time complexity for the depth-first search can be represented in form of O(V+E) where V is the number of vertices (or nodes) and E is the number of edges, or connections between these nodes. On the other hand, the space complexity of the algorithm is O(V) where V is once again the number of vertices or nodes.

Depth-first search can be useful in applications such as detecting a cycle in the graph, topological sorting or path finding. For example, DFS has been used in simulation games, whereby you could choose one of several possible actions. Each choice that is available could lead to further choices being made, of which these could lead to other choices. This is similar to an ever-expanding tree-shape graph, whereby a single node doubles to two nodes, which themselves have two nodes each attached to them, similar to a never-ending recursion loop.

Games like chess or tic-tac-toe often require some sort of decision to be made, normally depending upon the type of move you want to make. Any move you make would infer the choice of move to be made by the opposition, which would then affect your response etc. However, only some paths in this graph would ensure that you win your game, and computer AI opponents would often use a graph to represent all possible moves, and make use of the depth-first search algorithm to determine which move should be made next by traversing through a graph to find the solution.

Graph Traversal Algorithms (5)

Breadth-First Search (BFS)

Standard BFS implementation will put each vertex of the graph into one of two categories:
1. Visited
2. Not Visited (Queue)
The algorithm will mark each vertex as visited whilst avoiding cycles
The algorithm consists of the following steps:
1. Start by putting any one of the graph’s vertices to the back of a queue
2. Take the front item of the queue and add it to the visited list
3. Create a list of those vertices adjacent nodes and add any which are not in the visited list to the back of the queue
4. Keep repeating steps 2 and 3 until the queue is empty

Now we shall look at Breadth-first search. We have previously just looked at depth-first search, and you can probably guess how this algorithm will work. It works in a similar way by traversing the graph from the current vertex; and sometimes it is known as breadth first traversal.

We only move to the next vertex in the graph when we have examined all the edges. We look at all the edges and then look at those nodes; and then look at the nodes in order that we find them; before we can go to the node connected to them.

For example, if our starting node has three edges, each of those three edges will be examined first. Then we will go to the edges that come from the first node of those, and look at all of those edges and nodes, and so on. Whereas with the depth-first search, we always went along the edges until we could not traverse any further.

The algorithm works in the following steps:

We select a node to start from and put it to the back of the queue
We then take the front item of the queue and add it to the visited list
We then create a list of the vertices adjacent nodes and add any which are not in the visited list to the back of the queue
We keep repeating steps two and three until the queue is empty

Graph Traversal Algorithms (6)

BFS on an Undirected Graph

Click Start to proceed!

Unvisited

Visited

Lets walk-through the breadth-first search algorithm together on an undirected graph. On the right-hand-side of the screen, you can see that we have the graph that we wish to move through. We also have two stacks, one for the unvisited nodes, and the other for visited nodes. To begin our search, I am going to click the start button.

Click Start

We then need to observe the nodes that are connected to the node we are visiting. We therefore, explore the edges that we can follow, and we can see that the nodes B, C and D are connected and these nodes are added to our unvisited stack.

To progress, we pick the node at the top (or head as it is also known) of our unvisited stack, and proceed to visit the node.

Click Next

The next node we arrive at is node B and we add this node to our visited stack. Similar to the depth-first search algorithm, we perform a check to determine our unvisited neighbours. In this instance, there are no new neighbours that need to be added to our unvisited stack.

To progress, we pick the node at the top of our unvisited stack, and proceed to visit the node.

Click Next

The next node we arrive at is node C and we add this node to our visited stack. Once again, we perform a check to determine whether there are any new unvisited neighbours that we need to add to our unvisited stack. In this case, we do have a new neighbour, and that is node E.

However, this is where things are a little different. With the depth-first search algorithm, we added our nodes to the head of the stack. This time, we are doing different things, and we need to add our new nodes to the tail of the stack. You can see from our unvisited stack on the screen, that our nodes have been added to the bottom of our stack.

However, progression works as normal. Therefore, to progress, we pick the node at the top of our unvisited stack, and proceed to visit the node.

Click Next

The next node we arrive at is node D and we add this node to our visited stack. Once again, we perform a check to determine whether there are any new unvisited neighbours that we need to add to our unvisited stack. In this case, we have no new nodes we need to add to our stack.

The only connected node is node A and as this node has already been previously visited, it does not warrant being added to our unvisited stack again.

To progress, we pick the node at the top of our unvisited stack, and proceed to visit the node.

Click Next

The next node we arrive at is node E and we add this node to our visited stack. We can observe from this node, that the only connection is node C and as this node has previously been visited, we do not need to add this to our unvisited stack. As such, our unvisited stack is now empty, and we have completed our journey.

Click Next

Some key takeaways from this method of traversal, is that each node is visited to how it’s been populated in the unvisited stack. When you visit a node, and it needs to be added to the unvisited stack, it will be populated at the tail of the stack. The journey is continued until there are no more nodes left in the unvisited stack.

Graph Traversal Algorithms (7)

Time Complexity of BFS

The time complexity of BFS is represented in the form \(O(V + E)\), where
- \(V\) is the number of nodes
- \(E\) is the number of edges
The space complexity of BFS is \(O(V)\), where \(V\) is the number of nodes
BFS is useful in the following applications:
- shortest path in a graph (the least number of edges)
- peer to peer (P2P) networks
- search engine crawlers

Graph Theory Continued

Graph Theory Continued (1)

Recap: Directed Acyclic Graphs (DAG)

DAGs are directed graphs with no cycles
- hence the term acyclic
Testing for no cycles can be achieved by:
- a Depth-First Search (DFS)
- if a directed graph has a cycle, then a back arc will always be encountered in any depth-first search of the graph

A quick recap on direct acyclic graphs, these are directed graphs without a cycle. That does not mean you cannot have paths like those represented in the graph on the screen. Because, as it is directed, you cannot get back from one point to another, as all the paths are in one-direction and as such, there is no route to come back.

Therefore, how would we go about testing for no cycles? Well, we can use the depth-first search, and we can do this by looking to see if there is a way to get back to a certain point. If a directed graph has a cycle, a back arc will always be encountered in any depth-first search of the graph. Because as we keep going, we explore along the way we can go as far as we can. If we were to find that we ended up back at the starting point, then we found our back arc, and as such we have identified our DAG.

Graph Theory Continued (2)

Topological Sorting

A process of assigning a linear order to the vertices of a DAG
Time complexity is \(O(M+N)\), where
- \(M\) is the number of edges
- \(N\) is the number of nodes
Follows a set order of principles:
1. Identify a node with no incoming connections
2. Add that node to the topological sort list
3. Remove the node from the graph
4. Repeat

Topological Sort:
- ['F', 'C', 'D', 'B', 'A', 'E']
- ['F', 'C', 'D', 'B', 'E', 'A']

There are ways in which you can sort a directed, acyclic graph, and it is known as topological sorting. This is a process of assigning a linear order to the vertices of a DAG. The time complexity of topological sorting is O(M+N), and would be considered to be the fastest time we can expect as we are required to look at all nodes and connections that exist in the graph.

To work out the linear ordering of a graph, there is a set order of principles that you are required to follow.

The first step would be to identify a node that has zero incoming connections. To aid in doing this, you may want to revisit the previous lecture and consider creating a table of all in- and out-degrees of the graph. Once you have found a node with zero incoming connections, this would be the starting point on the graph.

The second step would be to add this node to a list, often referred to as a topological sort list. Once this node has been added to our list, the third step is to discard the node from our graph, albeit mentally.

The fourth step is simple, and that is to begin back at step one and repeat the process.

On the next slide, we shall walk through a graph and apply our topological sorting algorithm to it.

Graph Theory Continued (3)

Walkthrough: Topological Sorting

Click Start to proceed!

Lets walk-through the topological sorting algorithm together on a directed, acyclic graph. On the right-hand-side of the screen, you can see that we have the graph that we wish to move through. To begin our search, I am going to click the start button.

Click Start

We begin our journey by selecting a root node, and this is the node that we shall begin our journey from. In this case, we need to pick a node that has zero in-degrees; this means that the node will have no incoming connections. Therefore, for this example, our root node would be node B.

We add this node to our list, which can be seen at the bottom of the graph. Once we have added our node to the list, we can begin processing this node and the outgoing edges. We can then repeat our process from earlier and look for any nodes that have an in-degree of zero.

Click Next

In this case, the next node with an in-degree of zero taking the in-going connection from node B out of the equation, is node E. We select this node over node C, because as you can see, node C has an incoming connection from nodes E and A.

Therefore, we add node E to our topological sort list. Once we have added our node to the list, we can begin processing this node and the outgoing edges. We then repeat our process from earlier, and look for any nodes that have an in-degree of zero.

Click Next

In this case, the next node with an in-degree of zero taking the in-going connection from node E out of the equation, is node A. We select this node over node C, because as you can see, node C has an incoming connection from nodes E and A.

Therefore, we add node A to our topological sort list. Once we have added our node to the list, we can begin processing this node and the outgoing edges. We then repeat our process from earlier, and look for any nodes that have an in-degree of zero.

Click Next

In this case, the next node with an in-degree of zero taking the in-going connection from node E, and A out of the equation, is node C.

Therefore, we add node C to our topological sort list. Once we have added our node to the list, we can begin processing this node and the outgoing edges. We then repeat our process from earlier, and look for any nodes that have an in-degree of zero.

Click Next

In this case, the next node with an in-degree of zero taking the in-going connection from node A, and C out of the equation, is node D.

Therefore, we add node D to our topological sort list. Once we have added our node to the list, we can begin processing this node and the outgoing edges. We then repeat our process from earlier, and look for any nodes that have an in-degree of zero.

Click Next

Some key takeaways from this algorithm are that we shall always begin with a node that has zero incoming connections. Once this node has been added to our list, we shall mentally remove this node from our graph and then observe our graph again for nodes with an in-degree of zero. This process is constantly repeated until all nodes in our graph have been visited.

It is important to note that this is not the only method of working out the linear order for a graph. However, for any assessments or activities that require you to work out the linear order of a graph, this is the method I will be expecting you to use. It should also be said that a graph may have more than one topological order, as you can see from the previous slide, the graph had two linear orders.

Graph Theory Continued (4)

Density of Graphs

Graph density tells us how full the graph is
- i.e. how many connections exist in relation to the number of nodes
To formulate how dense a graph is, we need to know the size and order of a graph
- the size is the number of edges, \(|E|\)
- the order is the number of vertices, \(|V|\)

Sparse Graph

Dense Graph

There is terminology associated to graphs that denote how full they are, and this is often referred to as the density of a graph. They will be considered sparse if the number of edges is close to the minimal number of edges, whereas dense, on the other hand, is where the number of edges is closer to the maximal number of edges.

Consider the two graphs shown on the right-hand-side of the screen; you can see that the sparse graph has four edges connected to five nodes. However, the dense graph has eight edges for the same number of nodes, five. I will not go into much more detail regarding the mathematical notation behind this, but these are some terminologies that you should be familiar with when we discuss graphs.

Graph Theory Continued (5)

Spanning Trees

A spanning tree is a subgraph of an undirected, connected graph
- it will include all vertices of the graph with a minimum possible number of edges
- edges may contain weights or not
The total number of spanning trees is equal to \(n^{(n-2)}\)
- where \(n\) is the number of vertices

Example of a Spanning Tree

Normal Graph

Sub-Graphs

A spanning tree is a subgraph of an undirected and connected graph. It will include all the vertices of the graph with a minimum possible number of edges. However, if there is a vertex with no edge, then it will not be considered as a spanning tree. The edges of our tree may have weights assigned to them, but it is not essential if they do not.

The total number of spanning trees a graph may have can be calculated by the formula shown on the screen, where n is the number of vertices that exist in the graph. For example, if a graph were to have four nodes, then the number of spanning trees would be four to the power of four minus two, in this case, it would be sixteen.

On the screen, you will see an example of a spanning tree. On the left-hand-side, you will see our normal graph that consists of four nodes and four edges. On the right-hand-side, you will see two of the sixteen subgraphs that exist within the graph. Essentially, a subgraph is a version of our normal graph with an edge or more disconnected from it.

Graph Theory Continued (6)

Minimum Spanning Tree (MST)

A minimum spanning tree is a spanning tree whereby the minimum is the sum of weights that is the smallest

Sub-Graphs

Sum of Weights: 8

Sum of Weights: 7

Sum of Weights: 11

When it comes to finding a minimum spanning tree, we are concerned with the weight of a graph. In this case, we are concerned with finding the spanning tree whereby the minimum is the tree with the smallest sum of weights.

On the right-hand-side of the screen, next to the text, you can see our graph from earlier. However, this time we have associated some weights with our connections between the nodes. Below this, you can see a collection of subgraphs. These are three of the sixteen graphs that can be created from our graph. However, only one of these will be considered to be the minimum-spanning tree. In this instance, it is the middle graph, which has a total sum weight of seven.

Dijkstra’s Algorithm

Dijkstra’s Algorithm (1)

An algorithm to find the shortest path between nodes in a graph
Produces the shortest path tree
Works on both directed and non-directed graphs
- one condition: edges must have a non-negative weight
Simply, it is used to find the shortest path with the lowest cost
Dijkstra’s Algorithm can be applied to the following:
- Google Maps
- IP Routing
- Word Ladder Puzzles
- Social Network Analysis

Dijkstra’s algorithm is often applied to Graphs in order to find the shortest path between two nodes, and it was developed by Edsger Dijkstra in 1956. The original variant of this algorithm finds the shortest path between two nodes, but there is also a variant that fixes a single node as the source node and finds the shortest paths from the source to all other nodes in the graph and this will produce a shortest-path tree. If you were to look at the paths that were followed, you would not have any loops in them, as you disregard things you have seen already, unless they have a shorter path. This would result in a route being created through the graph that looks like a tree.

Dijkstra’s Algorithm (2)

Algorithm Steps

Mark all nodes in the graph as unvisited
Pick a starting node, and set the current distance as \(0\) and all other nodes with infinity
Select the starting node and mark it as the current selected node
- for this node, analyse all of its neighbours and measure their distances by summing the current distance
- this is done with the current node with the weight of the edge to the neighbouring node
Compare the measured distance with the current distance assigned to the neighbouring node
- mark this as the new current distance for the neighbouring node
Consider all the unvisited neighbouring nodes, and mark the current node as visited
- if the destination node has been marked as visited, then stop
- else choose an unvisited node marked with the least distance;
  - select it as the new current node and repeat the process from step 3

To understand how Dijkstra’s algorithm works, I have provided an itemized process of steps of how you would go about finding the shortest path in a graph.

The first step for our algorithm would be to mark all our nodes as unvisited. This may seem like a given, but it is always best to ensure we start off with a blank state. Once we have marked our nodes as unvisited, we can then pick our starting node and reset the current distance between this node and other nodes as infinity, along with the total distance covered as zero.

We take our starting node, and we mark this as visited, and add this node to a list of those that have been visited. We are now tasked with analysing all the neighbours and measuring their distance by summing the current distance between our starting node and the nodes that can be visited. The distance in this instance would be the weight associated to the edge connecting the two nodes.

We then look at comparing the measure distance with the current distance that is assigned to the neighbouring node. It will be noted as a new distance measure for that neighbouring node. We then need to consider all the unvisited neighbouring nodes, and mark the current node as visited only if the destination node has been marked as visited, and then we stop. Otherwise, we choose an unvisited node that is marked with the least distance and select it as our new current node. We then begin the process again from step 3.

Dijkstra’s Algorithm (3)

Walkthrough of Dijkstra

Click Start to proceed!

Unvisited

Visited

Lets walk-through an example of how Dijkstra’s algorithm works together. You can see on the screen a graph, with some connections and weights that are associated with them.

Click Start

We shall first begin with the root node, A. With this node, we shall check our adjacent neighbours and populate the table with our newly sought information. For node B, we populate the shortest distance as 6 as we can see that the distance between node A and B have a weight of 6 attributed to it. We also need to label the previous node that we were at if we were to travel this, and in this instance, we shall populate the cell with node A. We can repeat this for our second connected node, D. We populate the cells for the shortest distance and previous node as 1 and A, respectively.

Once the table has been populated with our details, we now check which one of these connected nodes have the shortest distance. In this instance, it is fairly easy to see that node D consists of the shortest distance with a weight of one associated to it. Therefore, we can now transition to this next node.

You will also note that for each node we have visited, we add it to the visited stack; and for any node that has not been visited, they are also added to their own stack of unvisited nodes. These are useful to keep track on how we are traversing through our graph.

Click Next

Now that we have moved to our second node, D, we repeat the same process as before. We check the nodes that are connected to node D and we update the values in our tables and stacks.

In this instance, we can see that node D is also connected to node B. Therefore, we need to update the shortest distance cost for this node. In this instance, we shall add the weight of the connection between nodes D to B onto the value previously in the table. What does this mean? Well simply, we are adding the value 1 and 2 together to get 3 and this will now be considered our shortest distance between node A and B. We then update our previous node cell in the table to be node D.

From the graph, we can see that we have a new node, and that is node E. Therefore, just like before, we need to update our table to show the cost of getting from node A to node E. For this node, we can transition from node A to D for a weighted cost of 1 and from node D to node E we can transition again for a weighted cost of 1. Therefore, the shortest distance value for this node is 2 and we label our previous node as D.

Click Next

Moving onto our third node, E, we now do the same process as last time and update our tables.

From node E we can visit nodes B and C. For node B, we can see that our shortest distance calculation for the path: A -> D -> E -> B, would be: 1 + 1 + 2 which would result in 4. However, this value is greater than the one that is already in our table, and we therefore discard this update; and leave the values as they are in the table.

Node C is a new node in our list, and we therefore, add up our shortest path weights, in this case, it would be: A(1) + D(1) + E(5) which results in 7, and we add our previous node label as node E.

Click Next

We are now at our fourth node, node B. From this node, we only have one unvisited node, and that is node C. You should know the drill by now; we need to go about updating the figures inside our table.

For node C we need to add up the weights for the path we have taken to get there. In this instance, the path is: A -> D -> E-> B -> C. Whereby the weights for each connection are: 1 + 1 + 2 + 5, which results in a grand total of 9. However, as this value is larger than what is already in our table, we can discard the path and leave it as it stands in our table.

And that is it, we have reached the end of our graph and visit all the possible nodes that we can.

From the working example, we have been able to work out the shortest path from node A to node C, and it is as follows:

A -> D -> E -> C

This is known as a greedy algorithm as the algorithm will always make a locally optimum choice at each stage. This is done in the hopes of finding a global optimum. With Dijkstra’s algorithm, we always choose the closest node to the tree in that instance, and then we restart the process.

Dijkstra’s algorithm has been used extensively in areas such as Google Maps, by helping you find the shortest distance #between one location to another. Whilst it can also be useful for IP routing, word ladder puzzles or social network analysis (remember Facebook’s Social Graph?).

Goodbye

Goodbye (1)

Questions and Support

Questions? Post them on the Community Page on Aula
Additional Support? Visit the Module Support Page
Contact Details:
- Dr Ian Cornelius, ab6459@coventry.ac.uk