Dijkstra algorithm – Mike Scherbakov

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(n²+m), where n – the number of vertices (nodes), m – the count of the edges

Space complexity: O(n²)

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"));
  }
}

Related Posts