Computer science is no more about computers than astronomy is about telescopes. - Edsger Dijkstra
There are many ways to find the shortest path between two points. A simple example would be driving instructions. Assuming a situation where traffic is not an issue, you could take literally thousands of different roadways to get from Massachusetts to California. So which one will get you there the quickest? To answer this question we must consider not only the time to travel between the two points, but also the time it takes to compute this information. Edsgar Dijkstra was responsible for creating the fastest algorithm to date that determines the quickest path between two points.
Dijkstra’s algorithm works on rather simple principles. The distance between the starting point and all adjacent points are first measured. The point at the shortest distance from the first point is then selected. This operation then repeats until the destination is reached.
The algorithm has been implemented in a plethora of modern programs. It is the base behind items such as Google Maps, GPS Devices, and network routing protocols where it is necessary for computers to communicate quickly with each other. The algorithm is also used in the computation of Fibonacci heaps, heap data structures in which each child key is greater than or equal to its parent.
Edsgar Dijkstra began college with the intent to major in theoretical physics, after realizing that physics was not for him, he then turned to computer science. He quickly became noted for his strong opinions about different aspects of programming. He has opposition against the programming language BASIC became quite prevalent after he stated that
“It is practically impossible to teach good programming to students that have had a prior exposure to BASIC: as potential programmers they are mentally mutilated beyond hope of regeneration.”
Dijkstra also denoted the idea of structure based controls such as using a while loop, before which there was a GOTO statement. He published a paper in 1968, urging developers to work towards the widespread usage of structured control constructs as well as the depreciation of the GOTO statement. The GOTO statement provided a one-way transfer of control from one line of code to another.
Note: In java goto is a reserved word but it is infact unusable.
Also noteworthy, Dijkstra created a fictional company, Mathematics Inc. for which he worked and published papers. The company mass produced mathematical formulas which it then sold to the public.
Pseudocode:
1 function Dijkstra(Graph, source):
2 for each vertex v in Graph: // Initializations
3 dist[v] := infinity ; // Unknown distance function from
4 // source to v
5 previous[v] := undefined ; // Previous node in optimal path
6 end for // from source
7
8 dist[source] := 0 ; // Distance from source to source
9 Q := the set of all nodes in Graph ; // All nodes in the graph are
10 // unoptimized - thus are in Q
11 while Q is not empty: // The main loop
12 u := vertex in Q with smallest distance in dist[] ; // Source node in first case
13 remove u from Q ;
14 if dist[u] = infinity:
15 break ; // all remaining vertices are
16 end if // inaccessible from source
17
18 for each neighbor v of u: // where v has not yet been
19 // removed from Q.
20 alt := dist[u] + dist_between(u, v) ;
21 if alt < dist[v]: // Relax (u,v,a)
22 dist[v] := alt ;
23 previous[v] := u ;
24 decrease-key v in Q; // Reorder v in the Queue
25 end if
26 end for
27 end while
28 return dist;
