Проблема с обходом графа - PullRequest
2 голосов
/ 18 октября 2010

Я реализовал алгоритм обхода графа, который находит путь между двумя узлами графа.Проблема в том, что он находит путь только для некоторых запросов, когда я знаю, что между каждым узлом есть путь

public List getDirectRoute(Node start, Node end)
{
    //Uses Dijkstras
    List<Node> vis = new LinkedList<Node>();
    Map<Node,Node> prev = new HashMap<Node,Node>(); // Records the previous Node

    List<Node> route = new LinkedList<Node>(); //Will hold the final route
    Queue<Node> queue = new LinkedList<Node>(); // Used for the algorithm 

    Node current = start;
    queue.add(current);
    vis.add(current);

    while(!queue.isEmpty())
    {
        current = queue.remove();

        if(current.equals(end))
        {
            break;
        }else
        {
            for(Node node : successors(current) )
            {
                if(node.equals(vertices.get(0)))
                {
                    continue;
                }
                if(!vis.contains(node))
                {
                    queue.add(node);
                    vis.add(node);
                    prev.put(node, current);
                 }
             }

           }
    }

    if (!current.equals(end))
    {
        System.out.println("No route available");
    }

    for(Node node = end; node != null; node = prev.get(node))
    {
        route.add(node);

    }
    return route;


}

Я что-то упустил в алгоритме?Я запустил отладчик и не могу найти проблему

Ответы [ 2 ]

1 голос
/ 18 октября 2010

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

0 голосов
/ 18 октября 2010

Похоже, вы используете поиск в ширину вместо алгоритма Дейкстры, чтобы найти путь от начала до конца.Я предполагал, что преемники возвращают текущие узлы, которые могут пройти, и vertices.get (0) означает, что узлы не имеют внешнего края к другим узлам.

Имея это в виду, похоже, ваш код должен работатьправильно.

Поэтому я должен сказать, что либо ваш метод-преемник работает неправильно, либо вы добавили вершины, у которых есть ребра к вершинам (0) (хотя это может содержать только 1 узел).

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

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...