Алгоритм Dijkstra для нахождения всех кратчайших путей возможными
Я работаю над алгоритмом Dijkstra, и я действительно должен найти все возможные кратчайшие пути, не всего один. Я использую матрицу смежности, и я применил алгоритм Dijkstra, и я могу найти кратчайший путь. Но я должен найти все пути с той минимальной стоимостью, я имею в виду все возможные решения, если они существуют.
Это - то, как мой алгоритм работает для единого решения:
public void dijkstra( int graph[][] )
{
int d[] = new int[ graph.length ];
int dC[] = new int[ graph.length ];
int p[] = new int[ graph.length ];
for( int i = 0; i < graph.length; i++ ){
d[ i ] = 100; dC[ i ] = 100; p[ i ] = -1;
}
d[ 0 ] = 0; dC[ 0 ] = 0;
int i = 0, min = 200, pos = 0; //You can change the min to 1000 to make it the largest number
while( i < graph.length ){
//extract minimum
for( int j = 0; j < dC.length; j++ ){
if( min > d[ j ] && dC[ j ] != -1 ){
min = d[ j ]; pos = j;
}
}
dC[ pos ] = -1;
//relax
for( int j = 0; j < graph.length; j++ ){
if( d[ j ] > graph[ pos ][ j ] + d[ pos ] ){
d[ j ] = graph[ pos ][ j ] + d[ pos ];
p[ j ] = pos;
}
}
i++; min = 200;
}
for( int j = 0; j < p.length; j++ ){
System.out.print( p[ j ] + " " );
}
System.out.print( "\n" );
for( int j = 0; j < d.length; j++ ){
System.out.print( d[ j ] + " " );
}
System.out.print( "\n" );
}
4 ответа
Если вы посмотрите здесь алгоритм Дейкстры в форме псевдокода: Википедия Псевдокод алгоритма Дейкстры
Вы заметите указанную строку чтобы расслабиться. Сейчас он содержит только случай, если найденный путь меньше текущего кратчайшего пути, но ничего не делается, если они равны . Вероятно, вам следует сохранить все одинаково короткие пути в списке.
Если ваша реализация алгоритма Дейкстры основана на очереди с приоритетами, возьмите первое решение, запишите глубину и продолжайте выдвигать решения, пока глубина не изменится.
Я не очень уверен, что алгоритм Дейкстры может быть легко адаптирован для этого; конечно, это не так просто, как удалить посещенные ребра, потому что n кратчайших могут разделять некоторые из них.
Поэтому почти грубая сила, но эвристически ориентированное решение заключается в следующем:
- для каждого ребра E в кратчайшем пути:
- удалить E и запустить модифицированный метод Дейкстры снова над новым графом
- если кратчайший путь длиннее первого полученного, остановиться
- в противном случае, повторить рекурсивное удаление одного ребра за раз из нового подграфа
Моя интуиция подсказывает мне, что это должно работать, с увеличением сложности пропорционально длине (n в количестве ребер) первого решения... Если нет больше кратчайших путей, то все должно закончиться на первом раунде, если найден другой, то продолжается с n-1 попыток. Оценка увеличения сложности в худшем случае по сравнению с оригинальным алгоритмом очень плохая (n! я полагаю?), но это также означает, что существует много путей, так что это работа, которую нужно проделать с любым алгоритмом...
edit: Подумав немного больше, увеличение сложности может быть даже больше, чем факториал числа узлов первого найденного пути, так как второй может иметь еще больше узлов! Поэтому я думаю, что очень трудно оценить сложность этого метода, но она должна быть чем-то вроде количество правильных решений умножить на среднее количество узлов в путях умножить на квадрат количества узлов (этот последний член - исходная сложность немодифицированного алгоритма).
edit 2: Я нашел научную статью на эту тему, для получения полного текста требуется подписка, но, возможно, вы сможете найти ее где-нибудь еще: http://ieeexplore.ieee.org/Xplore/login.jsp?reload=true&url=http%3A%2F%2Fieeexplore.ieee.org%2Fiel5%2F7719%2F21161%2F00982778.pdf%3Farnumber%3D982778&authDecision=-201
Если ваши графы допускают ребра с весом = 0 , а также допускают циклы, имейте в виду, что существует бесконечно много кратчайших путей, и вы не можете надеяться вывести их все!
Если нет ребер с нулевым весом или ваш граф является DAG, то ваше решение по-прежнему проблематично: оно либо не создает всех кратчайших путей, как требуется, либо делает это с O (2 ^ N) пространственная и временная сложность. Но тогда, возможно, будет столько же кратчайших путей, поэтому в общем случае нельзя надеяться на лучшее.
Это лучший источник для немного более общей проблемы: Поиск k кратчайших путей (Эпштейн). Вы можете применить это, перебирая кратчайшие пути, останавливаясь на первом пути, который длиннее предыдущего.
Для ограниченной задачи поиска только (эквивалентных) кратчайших путей указанная выше подсказка Андерсона Имеса (это домашнее задание? В противном случае кто-то должен ее разъяснить) хорош и намного проще, чем приведенный выше.