Since with graphs we can represent real-life problems it’s almost clear why we would need an efficient algorithm that calculates the shortest path between two vertices. Getting back to our example of a road map we can use such an algorithm in order to find the shortest path between two cities. This example, of course, is very basic indeed, but it can give us a clear example of where shortest path can be applied.
In the other hand, we can model an enormous field of real-life problems using graphs – not only road maps. As we already know, whenever we have relations between different abstract objects we can refer an efficient graph algorithm.
OK, so we need a shortest path algorithm, but before we proceed with the exact algorithm first we’ll need to answer some questions and give some definitions.
Overview
First we need a definition of the terms distance and path between two nodes. A path is considered to be the sequence of vertices (or edges if you wish) between two vertices i and j. Of course we assume that there might be no path between any to vertices in the graph! Also we assume that this definition relates both for directed and undirected graphs. After we have the definition of a path we can proceed by defining a “distance”, which is said to be the number of edges in the path between i and j.
Let’s assume we have a list of tasks to accomplish. Some of the tasks depend on others, so we must be very careful with the order of their execution. If the relationship between these tasks were simple enough we could represent them as a linked list, which would be great, and we would know the exact order of their execution. The problem is that sometimes the relations between the different tasks are more complex and some tasks depend on two or more other tasks, which in their turn depend on one or more tasks, etc.
Thus we can’t model this problem using linked lists or trees. The only rational solution is to model the problem using a graph. What kind of graph do we need? Well, we definitely need a directed graph, to desribe the relations, and this graph shouldn’t have cycles. So we need the so called directed acyclic graph (DAG).
In order to sort a graph using topological sort we need this graph to be acyclic and directed!
Why we don’t what a cycle in the graph? The answer of this question is simple and obvious. In case of cyclic graph, we wouldn’t be able to determine the priority of task execution, thus we won’t be able to sort the tasks properly.
Now the solution we want is to sort the vertices of the graph in some order so for each edge (u, v) u will precede v. Then we’ll have a linear order of all tasks and by starting their execution we’ll know that everything will be OK.
The output of topological sort should be a list of vertices!
So far we know how to implement graph depth-first and breadth-first search. These two approaches are crucial in order to understand graph traversal algorithms. However they are just explaining how we can walk through in breadth or depth and sometimes this isn’t enough for an efficient solution of graph traversal.
In the examples so far we had an undirected, unweighted graph and we were using adjacency matrices to represent the graphs. By using adjacency matrices we store 1 in the A[i][j] if there’s an edge between vertex i and vertex j. Otherwise we put a 0. However the value of 1 gives us only the information that we have an edge between two vertices, which is not always enough when designing graphs.
Indeed graphs can be weighted. Sometimes the path between two vertices can have a value. Thinking of a road map we know that distances between cities are represented in miles or kilometers. Thus often representing a road map as a graph, we don’t put just 1 between city A and city B, to say that there is a path between them, but also we put some meaningful information – let’s say the distance in miles between A and B.
Note that this value can be the distance in miles, but it can be something else, like the time in hours we’ve to walk between those two cities. In general this value is a function of A and B. So if we keep the distance between A and B we can say this function is F(A, B) = X, or distance(A, B) = X miles.
Of course in this particular example F(A, B) = F(B, A), but this isn’t always true in practice. We can have a directed graph where F(A, B) != F(B, A).
Here I talk about distance between two cities and it is the edge that brings some additional information. However sometimes we have to store the value of the vertices. Let’s say I’m playing a game (like chess) and each move brings me some additional benefit. So each move (vertex) can be evaluated with some particular value. Thus sometimes we don’t have a function of and edge like F(A, B), but function of the vertices, like F(A) and F(B).
In breadth-first search and depth-first search we just pick up a vertex and we consecutively walk through all its successors that haven’t been visited yet.
In order to walk through an unweithed graph using DFS, we chose consecutively each successor of node i!
So in DFS in particular we started from left to right in the array above. So the first node that has to be explored is vertex “1”.
0:[0,1,0,0,1,1]
0: [0, 1, 0, 0, 1, 1]
However sometimes, as I said above, we have weighted graphs, so the question is – is there any problem, regarding to the algorithm speed, if we go consecutively through all successors. The answer in general is yes, so we must modify a bit our code in order to continue not with the first but with the best matching successor. By best-matching we mean that the successor should match some criteria like – minimal or maximal value. Continue reading Computer Algorithms: Graph Best-First Search→
Along with breadth-first search, depth-first search is one of the two main methods to walk through a graph. This approach though is different. Breadth-first search (BFS) looks pretty much like starting from a vertex and expanding the searching process level by level. This means that first we get some information of all the successors of the given node and then we go further with the next level. In other words BFS is like a wave. Depth-first search is based on a different approach, which can be very useful in some specific algorithms.
Depth-first and breadth-first search are the two main ways to explore a graph!
Since we already know how to represent graphs, we can go further for some very simple approaches of walking through them. Passing by all the vertices of a graph is a fundamental technique for most of the graph algorithms, such as finding shortest/longest paths, etc.
First thing to note is that graphs are not trees, in most of the cases, so walking through them can’t start from a root, as we do with trees. What we must do first is to decide from where to start – in other words – choosing a starting vertex.
It’s clear that depending on the starting point we can get different passes through the graph. Thus choosing a starting point can be very important for our algorithm!
After that we need to know how to proceed. There are two approaches mostly known as “breadth first” and “depth first” search. While depth first search start from a vertex and goes as far as possible, then walks back and passes through vertices that haven’t been visited yet, breath first search is an approach of passing through all the neighbors of the node first, and then go to the next level. Continue reading Computer Algorithms: Graph Breadth First Search→
