Dijkstra in java
The Dijkstra algorithm has to do with graphs algorithms. This algorithm are made to find the shortest path from a given point (node) to another inside a weighted graph.
A weighted graph is a graph which its nodes are conected by edges with a given weight, called cost, every edge is one way directed. As the shown on the following figure:
In the graph we can see, to go from A node to C node there is an edge, a way, with a cost of 3 units, but to go from A to E there's no a directly way but it has to go trough another nodes, the question is: Which option has the lower cost? Going by the B, D or C node?
To solve the described question programmatically is by programing the Dijkstra algorithm.
The way I used its based on represent the graph by an adjacency array, where every weight is placed in a NxN array where N is the total nodes and where every cell, row with column intersect, has the weight of the edge from column node to row node. The graph from the previous figure becomes in an adjacency array this way:
The red values means there is not an edge or its a cycle (a way starting from a node and ending on same node).
I made the program on command line mode, it can read edge values one by one or the whole array from a flat text file, the previous array in a text file must be contain only the values, separated by a blank, no heads for column or rows, this way:
The run and output for the program (using the figure graph) gives this:
How many nodes has the graph to solve? 5
* Type the option number to load the graph:
1=From standar input (keyboard)
(The file must be flat text type and be formed by an nxn array where:
n=nodes number, the adjancecy array must have the following characteristics:
the edges are represented by its value, the unpresent edges and cicles by -1)
* Type the file's name to use:
* Which is the origin node: e
-> Results <-
Path: E->A weight: 5
Path: E->D->C->B weight: 9
Path: E->D->C weight: 7
Path: E->D weight: 5
<- Have a nice travel! ->
The program use two class, the source is following.