Как изменить алгоритмы поиска в ширину с одного потока на многопоточный? - PullRequest
Новая
       59

Как изменить алгоритмы поиска в ширину с одного потока на многопоточный?

0 голосов
/ 17 октября 2019

Я хочу получить кратчайший путь от одного узла к другому. Поэтому я использую алгоритмы поиска в ширину. Но в моем графике много узлов, и для получения результата мне понадобилось почти 300 секунд. Теперь мой менеджер спросит меняиспользовать многопоточный? Общий код здесь . Это необходимо? Как изменить мой код? Нужна ли какая-то параллельная среда, такая как Fork/Join? 

public int getShortestPath(Long beginLabel, Long endLabel,Stack<Vertex> stack) {
    Vertex begin = this.getVertexByLong(beginLabel);
    Vertex end = this.getVertexByLong(endLabel);
    begin.setVisited(true);
    List<Vertex> queue = new LinkedList<Vertex>();
    queue.add(begin);
    boolean done = false;
    while (!done && !queue.isEmpty()) {
        Vertex curVertex = queue.remove(0);
        StringBuffer sb = new StringBuffer();
        sb.append("curVertex:"+curVertex.getLabel()+"to>>>>>>");
        while (!done && curVertex.getFirstUnvisitedNeighbor() != null) {
            Vertex tmpVertex = curVertex.getFirstUnvisitedNeighbor();
            sb.append(tmpVertex.getLabel()+"|"); 
            tmpVertex.setVisited(true);
            int tmpCost = curVertex.getCost() + 1;
            tmpVertex.setPreviousVertex(curVertex);
            tmpVertex.setCost(tmpCost);
            queue.add(tmpVertex);
            if (tmpVertex.equals(end)) {
                done = true;
            }
        }
        sb.append(" end.");
        log.debug(sb.toString());
    }
    int pathLength = end.getCost();
    // find the path.traverse back from end
    while (end != null) {
        stack.push(end);
        end = end.getPreviousVertex();
    }
    return pathLength;
}
public Vertex getFirstUnvisitedNeighbor() {
    Vertex unVisitedNeighbor = null;
    for (int i = 0, len = edgeList.size(); i < len; i++) {
        Edge edge = edgeList.get(i);
        if(edge.isUnabled()){
            continue;
        }
        Vertex vertex = edge.endVertex;
        if (!vertex.isVisited) {
            unVisitedNeighbor = vertex;
            break;
        }
    }
    return unVisitedNeighbor;
}
...