Department of Computer Science Intro to Parallel Computing
Programming Assignment 3
Due Wednesday, October 28 at 6 pm
Dijkstra’s Algorithm
Edsger Dijkstra was a Dutch computer scientist. He is unquestionably one of the found-
ing fathers of computer science. In addition to devising Dijkstra’s algorithm, he was one
of the originators of structured programming | a precursor to modern object-oriented pro-
gramming. C, for example, is a structured programming language. He also made many
contributions to the solution of process-coordination problems in parallel computing: we’ll
learn about several later on in the course. His Wikipedia page lists more than fty funda-
mental contributions to computer science.
Dijkstra’s algorithm solves the single-source shortest path problem” in a weighted, di-
rected graph. The input consists of a weighted, directed graph and a specied vertex in the
graph. A directed graph or digraph is a collection of vertices and directed edges, which join
one vertex to another. A weighted dig