How to make Dijkstra's algorithm parallel?

Question

Java

Hello. Please help me parallelize Dijkstra's algorithm. Generally no idea how to do it.

public class DijkstraAlgorithm {

    public static final Node Minimum_Unknown = null;
    private Set<Node> settledNodes;
    private Map<Node, Node> predecessors;
    private Map<Node, Integer> distanceByNode;
    private final Graph graph;

    public DijkstraAlgorithm(Graph graph) {
        this.graph = graph;
    }

    public void execute(Node source) {
        settledNodes = new HashSet<Node>();
        distanceByNode = new HashMap<Node, Integer>();
        predecessors = new HashMap<Node, Node>();
        distanceByNode.put(source, 0);
        while (!getUnsettledNodes().isEmpty()) {
            Node node = getNodeWithMinimalDistanceToSourceFromUnsettledNodes();
            settledNodes.add(node);
            findMinimalDistancesFromNodeToNeighbors(node);
        }
    }

    private void findMinimalDistancesFromNodeToNeighbors(Node node) {
        for (Node target : getNeighbors(node)) {
            int distanceToTargetViaNode = getShortestDistance(node) + getDistance(node, target);
            if (getShortestDistance(target) > distanceToTargetViaNode) {
                distanceByNode.put(target, distanceToTargetViaNode);
                predecessors.put(target, node);
            }
        }
    }

    private int getDistance(Node source, Node target) {
        for (Edge edge : getEdges()) {
            if (edge.connects(source, target)) {
                return edge.getWeight();
            }
        }
        return MAX_VALUE;
    }

    private List<Node> getNeighbors(Node node) {
        List<Node> neighbors = node.getNeighbours(getEdges());
        neighbors.removeAll(settledNodes);
        return neighbors;
    }

    private Node getNodeWithMinimalDistanceToSourceFromUnsettledNodes() {
        Node minimum = null;
        for (Node node : getUnsettledNodes()) {
            if (getShortestDistance(node) < getShortestDistance(minimum)) {
                minimum = node;
            }
        }
        return minimum;
    }

    private int getShortestDistance(Node destination) {
        return distanceByNode.containsKey(destination) ? distanceByNode.get(destination) : MAX_VALUE;
    }

    public List<Node> getPath(Node target) {
        boolean isConnected = predecessors.containsKey(target);
        if (isConnected) {
            return constructPath(target);
        }
        return new LinkedList<Node>();
    }

    private List<Node> constructPath(Node step) {
        List<Node> path = new LinkedList<Node>();
        path.add(step);
        while (predecessors.containsKey(step)) {
            step = predecessors.get(step);
            path.add(step);
        }
        reverse(path);
        return path;
    }

    private List<Edge> getEdges() {
        return graph.getEdges();
    }

    private Set<Node> getUnsettledNodes() {
        Set<Node> nodes = new HashSet<Node>(distanceByNode.keySet());
        nodes.removeAll(settledNodes);
        return nodes;
    }
}

Answer 1

If the algorithm, like yours, is implemented without a heap, then you can stupidly parallelize 2 main functions - getNodeWithMinimalDistanceToSourceFromUnsettledNodes and findMinimalDistancesFromNodeToNeighbors.
And there, and there - one cycle. If the number of threads is not too large, then almost full speedup can be achieved by loading all the cores. The first function - just each thread is looking for a minimum on its subsection of the array. At the end, the main thread takes the minimum of these several values. The second function is also parallelized - each thread updates the distances for some part of all neighbors (neighbors must be stored in an array in this case).
But in general, other algorithms are more suitable for parallelization - Ford-Folkerson, for example. There can be a lot of threads here, and although a non-parallel algorithm is slower than Dijkstra, with a large number of threads it can be faster.