Использование Dijkstra для обнаружения нескольких кратчайших путей - PullRequest
Новая
       59

Использование Dijkstra для обнаружения нескольких кратчайших путей

0 голосов
/ 18 мая 2018

Учитывая взвешенный ориентированный граф, как можно изменить алгоритм Дейкстры для проверки наличия нескольких путей с наименьшей стоимостью между данной парой узлов?

Мой текущий алгоритм выглядит следующим образом: (кредитВайс) 

/**
 * Single-source weighted shortest-path algorithm. (Dijkstra) 
 * using priority queues based on the binary heap
 */
public void dijkstra( String startName )
{
    PriorityQueue<Path> pq = new PriorityQueue<Path>( );

    Vertex start = vertexMap.get( startName );
    if( start == null )
        throw new NoSuchElementException( "Start vertex not found" );

    clearAll( );
    pq.add( new Path( start, 0 ) ); start.dist = 0;

    int nodesSeen = 0;
    while( !pq.isEmpty( ) && nodesSeen < vertexMap.size( ) )
    {
        Path vrec = pq.remove( );
        Vertex v = vrec.dest;
        if( v.scratch != 0 )  // already processed v
            continue;

        v.scratch = 1;
        nodesSeen++;

        for( Edge e : v.adj )
        {
            Vertex w = e.dest;
            double cvw = e.cost;

            if( cvw < 0 )
                throw new GraphException( "Graph has negative edges" );

            if( w.dist > v.dist + cvw )
            {
                w.dist = v.dist +cvw;
                w.prev = v;
                pq.add( new Path( w, w.dist ) );
            }
        }
    }
}

Ответы [ 2 ]

0 голосов
/ 18 мая 2018

Замените поле prev, ссылку на предыдущую вершину коллекцией prevs, и немного измените код: 

...

        if( w.dist >= v.dist + cvw ) {
            if ( w.dist > v.dist + cvw ) {
                w.dist = v.dist +cvw;
                w.prevs.clear();
            }
            w.prevs.add(v);
            pq.add( new Path( w, w.dist ) );
        }

...
0 голосов
/ 18 мая 2018

Если вы хотите найти только один другой путь равной стоимости

Предположим, вы уже один раз запускали алгоритм Дейкстры, чтобы получить кратчайший путь P.Вы можете добавить крошечную стоимость epsilon к каждому ребру в P и запустить Дейкстру во второй раз на измененном графике, чтобы получить новый путь P'.Если P и P' содержат одинаковые ребра, вы можете сделать вывод, что P - это уникальный кратчайший путь.В противном случае мы отменяем изменение epsilon и сравниваем длины P и P'.Если длины равны, то ясно, что P' - это другой отличный кратчайший путь.В противном случае P является уникальным кратчайшим путем.

Если мы хотим найти все кратчайшие пути

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

A --> B1 --> C --> D1 --> E ...
  \       ->   \       ->
   -> B2 /      -> D2 /

Существует 4 пути от A до E, и если мы предположим, что все ребра имеют одинаковую стоимость, то все эти пути имеют одинаковую общую стоимость.Повторяя этот шаблон, мы можем получить экспоненциально множество путей одинаковой стоимости.

...