Как сделать алгоритм Дейкстры параллельным?

Question

[parkito]

Здравствуйте. Помогите, пожалуйста, распаралелить алгоритм Дейкстры. Вообще идей нету как это можно сделать.

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

[Wataru]

Если алгоритм, как у вас, реализован без кучи, то можно втупую распаралелить 2 основные функции - getNodeWithMinimalDistanceToSourceFromUnsettledNodes и findMinimalDistancesFromNodeToNeighbors.
И там, и там - один цикл. Если количество потоков не слишком большое, то можно достичь почти полного ускорения, загрузив все ядра. Первая функция - просто каждый поток ищет минимум на своем подотрезке массива. В конце, основной поток из этих нескольких значений берет минимум. Вторая функция так же параллелится - каждый поток обновляет расстояния для некоторой части всех соседей (соседи должны в этом случае храниться в массиве).

Но вобще, для параллелизации больше подходят другие алгоритмы - форда-фолкерсона, например. Тут может быть очень много потоков, и хоть непараллельный алгоритм медленее дейкстры, при большом количестве потоков может быть быстрее.