The Dijkstra algorithm serves to find the cheapest path in acyclic graphs with positive weights.
The algorithms can be described as following actions:
- Introduce 2 maps:
– the costs to store the minimum cost of reaching a node from the starting node
– the parents to store the shortest path. - Introduce a list of processed nodes.
- Start with the cheapest and not processed node (according to the map costs and the list of processed nodes).
- Find all neighbors of the current node.
- Update costs and parents maps if the path through the current node is cheaper than it was.
- Put the current node to the list of processed node.
- Recursively start from point 3.
- After processing, we will have to maps: with the cheapest path from the starting node to all nodes, and the map describing the shortest path from start to finish.
Time complexity: O(n2+m), where n – the number of vertices (nodes), m – the count of the edges
Space complexity: O(n2)
import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class ImplementDijkstraAlgorithm {
private static final Map<String, Map<String, Integer>> graph = Map.of(
"start", Map.of("a", 6, "b", 2),
"a", Map.of("fin", 1),
"b", Map.of("a", 3, "fin", 5),
"fin", Map.of()
);
private static final Map<String, Integer> costs = new HashMap<>() {
{
put("a", 6);
put("b", 2);
put("fin", Integer.MAX_VALUE);
}
};
private static final Map<String, String> parents = new HashMap<>() {
{
put("a", "start");
put("b", "start");
put("fin", null);
}
};
private static final List<String> processed = new ArrayList<>();
private static String findLowestNodeCost() {
return costs.entrySet().stream()
.filter(entry -> !processed.contains(entry.getKey()))
.sorted(Comparator.comparingInt(Map.Entry::getValue))
.map(Map.Entry::getKey)
.findFirst().orElse(null);
}
public static void main(String[] args) {
var node = findLowestNodeCost();
while (node != null) {
var neighbors = graph.get(node);
var cost = costs.get(node);
for (var entry : neighbors.entrySet()) {
var newCost = cost + entry.getValue();
if (newCost < costs.get(entry.getKey())) {
costs.put(entry.getKey(), newCost);
parents.put(entry.getKey(), node);
}
}
processed.add(node);
node = findLowestNodeCost();
}
System.out.println(costs.get("fin"));
}
}
Pingback: Bellman-Ford algorithm – Mike Scherbakov