Tag Archives: Routing algorithms

Computer Algorithms: Longest Increasing Subsequence

algorithms, data structures, dynamic programming, Graphs, , , , , , , , , , , , , , , , , ,

Introduction

A very common problem in computer programming is finding the longest increasing (decreasing) subsequence in a sequence of numbers (usually integers). Actually this is a typical dynamic programming problem.

Dynamic programming can be described as a huge area of computer science problems that can be categorized by the way they can be solved. Unlike divide and conquer, where we were able to merge the fairly equal sub-solutions in order to receive one single solution of the problem, in dynamic programming we usually try to find an optimal sub-solution and then grow it.

Once we have an optimal sub-solution on each step we try to upgrade it in order to cover the whole problem. Thus a typical member of the dynamic programming class is finding the longest subsequence.

However this problem is interesting because it can be related to graph theory. Let’s find out how. Continue reading Computer Algorithms: Longest Increasing Subsequence →

Computer Algorithms: Shortest Path in a Directed Acyclic Graph

algorithms, data structures, Graphs, , , , , , , , , , , , , ,

Introduction

We saw how to find the shortest path in a graph with positive edges using the Dijkstra’s algorithm. We also know how to find the shortest paths from a given source node to all other nodes even when there are negative edges using the Bellman-Ford algorithm. Now we’ll see that there’s a faster algorithm running in linear time that can find the shortest paths from a given source node to all other reachable vertices in a directed acyclic graph, also known as a DAG.

Because the DAG is acyclic we don’t have to worry about negative cycles. As we already know it’s pointless to speak about shortest path in the presence of negative cycles because we can “loop” over these cycles and practically our path will become shorter and shorter.

Negative Cycles
The presence of a negative cycles make our atempt to find the shortest path pointless!

Thus we have two problems to overcome with Dijkstra and the Bellman-Ford algorithms. First of all we needed only positive weights and on the second place we didn’t want cycles. Well, we can handle both cases in this algorithm. Continue reading Computer Algorithms: Shortest Path in a Directed Acyclic Graph →

Computer Algorithms: Bellman-Ford Shortest Path in a Graph

algorithms, data structures, Graphs, , , , , , , , , , , , , ,

Introduction

As we saw in the previous post, the algorithm of Dijkstra is very useful when it comes to find all the shortest paths in a weighted graph. However it has one major problem! Obviously it doesn’t work correctly when dealing with negative lengths of the edges.

We know that the algorithm works perfectly when it comes to positive edges, and that is absolutely normal because we try to optimize the inequality of the triangle.

Dijkstra's Approach
Since all the edges are positive we get the closest one!

Since Dijkstra’s algorithm make use of a priority queue normally we get first the shortest adjacent edge to the starting point. In our very basic example we’ll get first the edge with the length of 3 -> (S, A).

However when it comes to negative edges we can’t use any more priority queues, so we need a different, yet working solution. Continue reading Computer Algorithms: Bellman-Ford Shortest Path in a Graph →

Computer Algorithms: Dijkstra Shortest Path in a Graph

algorithms, data structures, Graphs, , , , , , , , , , , , , , , , , ,

Introduction

We already know how we can find the shortest paths in a graph starting from a given vertex. Practically we modified breadth-first search in order to calculate the distances from s to all other nodes reachable from s. We know that this works because BFS walks through the graph level by level.

BFS Shortest Paths
BFS is often used to find shortest paths between a starting node (s) and all other reachable nodes in a graph!

Some sources give a very simple explanation of how BFS finds the shortest paths in a graph. We must just think of the graph as a set of balls connected through strings.

The Graph as Balls and Strings
We can think of a graph as a set of balls connected through strings!

As we can see by lifting the ball called “S” all other balls fall down. The closest balls are directly connected to “s” and this is the first level, while the outermost balls are those with longest paths.

The Graph as Balls and Strings Levels
Breadth-first search works much like the image above – it explores the graph level by level, thus we’re sure that all the paths are the shortest!

Clearly edges like those between A and B doesn’t matter for our BFS algorithm because they don’t make the path from S to C through B shorter. This is also known as the triangle inequality, where the sum of the lengths of two of the sides of the triangle is always greater than the length of the third side.

Triangle inequality
What the triangle inequality says us is that if we have a direct edge between two nodes – that must be the shortest path between them!

We must only answer the question is BFS the best algorithm that finds the shortest path between any two nodes of the graph? This is a reasonable question because as we know by using BFS we don’t find only the shortest path between given vertices i and j, but we also get the shortest paths between i and all other vertices of G. This is an information that we actually don’t need, but can we find the shortest path between i and j without that info? Continue reading Computer Algorithms: Dijkstra Shortest Path in a Graph →

Computer Algorithms: Shortest Path in a Graph

algorithms, data structures, Graphs, , , , , , , , , , , , , , , , , , , ,

Introduction

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.

Path and Distance
First we need to define what’s a path and a distance between two vertices in order to continue searching for the shortest path!
Continue reading Computer Algorithms: Shortest Path in a Graph →