3 - Dijkstra's single source shortest path algorithm

This is an algorithm every computer course student will remember until the Alzheimer or the alcohol had killed enough brain cells. If not by its application, then by its author's name that is really cool :)

Single source shortest path algorithms are very useful to everyone without doubt, because can be used to determine the best route from a starting point to other points in a graph. Imagine then this graph like the streets in your city. Now you can know the best path from your house to the supermarket.

There are variations of the problem (more than one path, more then one starting point, etc) and therefore several solutions,  but I've chosen Dijkstra's algorithm because it is a classic solution for a classic problem (ok, first because my good friend Lourenço asked me) : finding the best possible path between a source and a destination, once given several possible paths.

Before showing the algorithm some conditions must be stated:

1. the algorithm assume that the problem is represented as a graph;


2. the graph must be a directed graph (no cycles allowed);


3. the graph's edges must be weighted always with positive values;

Considering this, given a graph G=(V,E), all vertexes in V must be initialized as  infinite because in the first state we don't know the minimum distance from the source to any given destination. The exception it the origin who must be tagged as zero (the distance between the origin and itself).

The algorithm will then loop through all vertexes picking the one with the minimum shortest path (in the first iteration the origin will be selected), until all the vertexes in V are selected. When selected, the vertex is stored in a set S, which on the end will hold the vertexes that compose the shortest path. The selection of each vertex is usually implemented as a min-priority queue that will dictate the algorithm's performance.

For each selected vertex, its successors must be tagged with the costs for going from the source until that specific successor. This cost is nothing more that the sum of the edge weight with the value previously attributed to the selected vertex, and the tagging is done only if the new cost is less than a previous attributed cost.

Mr. Cormen [1] refers to this processes as relaxation, and I took the liberty of reproducing bellow (hopefully I won't be sued) the pseudo-code for Dijkstra's that appears in Introduction to Algorithms (second edition).

DIJKSTRA(G, w, s)
1  INITIALIZE-SINGLE-SOURCE(G, s)
2  S ← Ø
3  Q ← V[G]
4  while Q ≠ Ø
5      do u ← EXTRACT-MIN(Q)
6         S ← S ∪{u}
7         for each vertex v ∈ Adj[u]
8             do RELAX(u, v, w)

RELAX(u, v, w)
1  if d[v] > d[u] + w(u, v)
2     then d[v] ← d[u] + w(u, v)
3          π[v] ← u

INITIALIZE-SINGLE-SOURCE(G, s)
1  for each vertex v ∈ V[G]
2       do d[v] ← ∞
3          π[v] ← NIL
4  d[s] 0

This page has some very illustrative Java applets that show the algorithm in action.

The algorithm has a wide usage when determining distance costs - I would not be surprised if Google were using it in Google Maps :) - but it can also be used to solve another problems that can be specified as nodes and weighted transitions. One example would be finding the best possible move in a chess match, where each possible move would be a vertex and the cost of each move (from the chess-master point of view) would be an edge weight.

There are also some works on solving the Rubik's cube problem using Dijkstra's single source shortest path algorithm, like this one here.

References:

1. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms (McGraw-Hill Science / Engineering / Math, 2003), second edn.

2 - The "midpoint" curve-drawing algorithm

This is another algorithm well known in the computer graphics world. And it is here because, the same way that drawing straight lines,  drawing curved lines is important.

Being said as a variation of Brasenham's algorithm, the midpoint curve drawing algorithm was first described by Pitteway in 1967. Again, it is an old piece of computer science that integrates the graphics circuits until today.

Drawing must be fast ever and the problems found in drawing curves  are the same as drawing lines. One could say that it is even harder.

So the curve drawing algorithm is bright cause it uses only integers additions and multiplications (of course you can represent all multiplications as additions) and uses an ingenious strategy  to avoid calculations with floating points.

The main idea is to split the circle (actually works for any elliptical shape) in 8 slices, called octants. Each octant represents 45 degrees of a curve. Then, for each octant, there's a point P starting at (x,y) where the drawing will start. The next point is given by the circle equation f(x,y)=x^2 +y^2 - r^2. This is evaluated for each iteration, until the ellipse is completed the direction of the drawing (x and/or y going up or down) is related to the octant and the value of f.

I could not find the original paper for download, but it is available for  members of The Computer Journal here. More details on how the algorithm can be implemented can be found in most basic computer graphics books. And of course there is an implementation at wikipedia that seems very nice.

Thank you for your time

1- The first one: bright, clean and really useful

Have I told you that my area of expertise is Computer Graphics? Well, now you know.

So, for that matter, our first algorithm should be CG related. I've chosen one that everybody can ascertain its existence. May I present you the Line Drawing Bresenham's Algorithm.

Given 2 points in a discrete plane, this algorithm draws a line connecting these two points. Have you ever thought about how the lines are draw in your amazing GUI? Well, it is done by connecting sequential pixels, which is easy if the line is absolutely horizontal or vertical. But if the line has some slope, than we need a line drawing algorithm.

In first place, this algorithm could be used in every computer system today, so even a plant could agree that it is useful (right, I can tell if this algorithm was really used in a raster computer system like the ones implemented Next or X11, but could be it or some variation/evolution. Some graphics cards do implement line drawing algorithms based on the original Bresenham code).

The algorithm is was first written in 1962, and the paper was published in 1965 at IBM Systems Journal. Then, in a world where computing power was very very expensive, floating point calculations were yet more expensive (no, no hardware acceleration kids), and the work had to get done, this algorithm came to be perfect.

It is great cause avoid floating point calculations, multiplications and fractions. So, using just addition and subtraction with integer numbers (some implementations use bit shift to accomplish integer multiplication/division by 2, which is fast even on simple processors) the algorithm is also really fast. It works trying to draw the perfect line by finding the next pixel to draw. As more the one pixel can be chosen, the algorithm select the best by attributing errors to each option. The one pixel with the best error value is next in the line.

I have coded myself this algorithm during my Bachelors, but of course I have not this code anymore. Wikipedia has an implementation here that, to me, looks correct.  Also the original (first implementation) can be found here,  and the paper here.

With all of theses positive points, our number one take leave of our presence, thank you and say to wait for the next one in the line.

References: Jack E. Bresenham, Algorithm for Computer Control of a Digital Plotter, IBM Systems Journal, 4(1):25-30, 1965. On-line at http://researchweb.watson.ibm.com/journal/sj/041/ibmsjIVRIC.pdf
Reprinted in Interactive Computer Graphics, Herbert Freeman ed., 1980, and Seminal Graphics: Pioneering Efforts That Shaped The Field, Rosalee Wolfe ed., ACM SIGGRAPH, 1998.