A Collection of Code Snippets in as Many Programming Languages as Possible
This project is maintained by TheRenegadeCoder
Welcome to the Dijkstra page! Here, you'll find a description of the project as well as a list of sample programs written in various languages.
Dijkstra's algorithm (or Dijkstra's Shortest Path First algorithm, SPF algorithm) is an algorithm for finding the shortest paths between nodes in a graph, which may represent, for example, road networks. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years later.
Dijkstra's algorithm doesn't work for graphs with negative weight edges.
Below are the detailed steps used in Dijkstra's algorithm to find the shortest path from a single source vertex to all other vertices in the given graph.
Dijkstra's algorithm to find the shortest path between a and b. It picks the unvisited vertex with the low distance, calculates the distance through it to each unvisited neighbor, and updates the neighbor's distance if smaller. Mark visited (set to red) when done with neighbors.
./dijkstra.lang "0, 2, 0, 6, 0, 2, 0, 3, 8, 5, 0, 3, 0, 0, 7, 6, 8, 0, 0, 9, 0, 5, 7, 9, 0" "0" "1"
Here we've chosen to represent the matrix as a serialized list of integers. Since the input string represents a square matrix, we should be able to take the square root of the length to determine where the rows are in the string. In this case, we have 25 values, so we must have 5 nodes. If we reformat the input string as a matrix, we'll notice that the values in the matrix represent the edge weight between each node. For example, we could reformat our example to look something like the following:
Mapping | 0 | 1 | 2 | 3 | 4 |
---|---|---|---|---|---|
0 | 0 | 2 | 0 | 6 | 0 |
1 | 2 | 0 | 3 | 8 | 5 |
2 | 0 | 3 | 0 | 0 | 7 |
3 | 6 | 8 | 0 | 0 | 9 |
4 | 0 | 5 | 7 | 9 | 0 |
Then we take the Source and the Destination.
The Output will be the Cost of the Shortest Path from Source to Destination.
Every project in the Sample Programs repo should be tested. In this section, we specify the set of tests specific to Dijkstra. To keep things simple, we split up testing into two subsets: valid and invalid. Valid tests refer to tests that occur under correct input conditions. Invalid tests refer to tests that occur on bad input (e.g., letters instead of numbers).
Description | Matrix | Source | Destination | Output |
---|---|---|---|---|
Proper Input | "0, 2, 0, 6, 0, 2, 0, 3, 8, 5, 0, 3, 0, 0, 7, 6, 8, 0, 0, 9, 0, 5, 7, 9, 0" |
"0" |
"1" |
2 |
Description | Matrix | Source | Destination |
---|---|---|---|
No Input | |||
Empty Input | "" |
"" |
"" |
Non-Square Input | "1, 0, 3, 0, 5, 1" |
"1" |
"2" |
No Destination | "0, 2, 0, 6, 0, 2, 0, 3, 8, 5, 0, 3, 0, 0, 7, 6, 8, 0, 0, 9, 0, 5, 7, 9, 0" |
"0" |
"" |
No Source and Destination | "0, 2, 0, 6, 0, 2, 0, 3, 8, 5, 0, 3, 0, 0, 7, 6, 8, 0, 0, 9, 0, 5, 7, 9, 0" |
"" |
"" |
The Source or The Destination < 0 | "0, 2, 0, 6, 0, 2, 0, 3, 8, 5, 0, 3, 0, 0, 7, 6, 8, 0, 0, 9, 0, 5, 7, 9, 0" |
"-1" |
"2" |
The Source or The Destination < 0 | "0, 2, 0, 6, 0, 2, 0, 3, 8, 5, 0, 3, 0, 0, 7, 6, 8, 0, 0, 9, 0, 5, 7, 9, 0" |
"-1" |
"2" |
Weight < 0 | "0, 2, 0, -6, 0, 2, 0, 3, 8, 5, 0, 3, 0, 0, 7, -6, 8, 0, 0, 9, 0, 5, 7, 9, 0" |
"1" |
"2" |
The Source or The Destination > SquareRootOfMatrix - 1 | "0, 2, 0, 6, 0, 2, 0, 3, 8, 5, 0, 3, 0, 0, 7, 6, 8, 0, 0, 9, 0, 5, 7, 9, 0" |
"1" |
"10" |
No way | "0, 0, 0, 0" |
"0" |
"1" |
All invalid tests should spit out a usage statement in the following form:
Usage: please provide three inputs: a serialized matrix, a source node and a destination node