15 / 14 / 10
Регистрация: 22.03.2010
Сообщений: 695
1

Распаралелить алгоритм нахождения кратчайшего пути

09.05.2017, 05:16. Показов 365. Ответов 1
Метки нет (Все метки)

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

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
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;
    }
}
__________________
Помощь в написании контрольных, курсовых и дипломных работ здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
09.05.2017, 05:16
Ответы с готовыми решениями:

Задача нахождения кратчайшего пути
Никак не могу понять почему в таких типах задач у меня ошибка. Помогите найти ошибку, и если...

Составить программу нахождения самого кратчайшего пути
Описание Петя долго что-то чертил на небольшом листе в клетку, после чего, продемонстрировал его...

Граф и реализация алгоритмов нахождения кратчайшего пути
Пожалуста,помогите!Как создать граф в для реализации на нем разных алгоримов нахождения кратчайшего...

Составить программу для нахождения кратчайшего пути парохода
Пароход должен пройти из пункта М в пункт Н,обойдя препятствие,имеющее вид отрезка АВ.Составить...

1
Эксперт Java
3338 / 2773 / 853
Регистрация: 05.07.2013
Сообщений: 13,296
09.05.2017, 12:42 2
google->parallel dijkstra java
https://github.com/gsnorton/Parallel-Dijkstra
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
09.05.2017, 12:42

Алгоритм кратчайшего пути
Всем привет. Посоветуйте - как решить задачу. Есть теоретический алгоритм трассировки печатных...

Алгоритм А* (Нахождение кратчайшего пути)
http://wiki.linuxformat.ru/index.php/LXF72:PHP#.D0.BD.D1.83_.D1.82.D0.B5.D0.BF.D0.B5.D1.80.D1.8C_.D0...

Алгоритм поиска кратчайшего пути
Возникла необходимость написать программу поиска кратчайшего пути между некоторыми связанными между...

Написать программу для нахождения кратчайшего пути между заданными вершинами графа
visual studio windows forms нужна программа,которая будет вычислять кратчайший путь от вершины a...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru