Алгоритм Дейкстры, чтобы найти наиболее взвешенный путь

Question

Я просто хочу убедиться, что это сработает.Не могли бы вы найти лучший путь, используя алгоритм Дейкстры?Придется ли вам сначала инициализировать расстояние примерно до -1, а затем изменить подпрограмму relax, чтобы проверить, больше ли она?

Это для задачи, которая не будет иметь отрицательных весов.

Это на самом деле проблема:

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

Будет ли это работать?

---

РЕДАКТИРОВАТЬ:

Я нашел это:

Подсказка: основная подпрограмма будет очень похожа на подпрограмму Relax в Dijkstra.Предположим, что у нас есть ребро (u, v).Если min {d [u], w (u, v)}> d [v], то мы должны обновить d [v] до min {d [u], w (u, v)} (потому что путь от a доu, а затем v имеет пропускную способность min {d [u], w (u, v)}, что больше, чем у нас в настоящее время).

Не совсем уверен, что это значитхотя, так как все расстояние это бесконечность при инициализации.Итак, я не знаю, как это будет работать.какие-нибудь подсказки?

Answer 1

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

Вам не нужно инициализировать начальную вершину -1.

Algorithm: Maximum Bandwidth(G,a)

Input: A simple undirected weighted graph G with non -ve edge weights, and a distinguished     vertex a of G

Output: A label D[u], for each vertex u of G, such that D[u] is the maximum bandwidth available from a to u.


Initialize empty queue Q;
Start = a;
for each vertex u of G do,
   D[u] = 0;

for all vertices z adjacent to Start do{                              ---- 1

 If D[Start] => D[z] && w(start, z) > D[z] {
    Q.enqueue(z);
    D[z] = min(D[start], D[z]);
  }
}
If Q!=null {
   Start = Q.dequeue;
   Jump to 1

}

else
  finish();

Возможно, это не самый эффективный способ расчета пропускной способности, но это то, о чем я мог бы подумать сейчас.

Answer 2

Я не уверен, что Джикстра это путь. Отрицательные веса плохо влияют на Джикстру.

Я думаю, что вы могли бы отсортировать по весу ребра и начать удаление ребра с наименьшим весом (наихудшее узкое место), и посмотреть, подключен ли график (или, по крайней мере, ваши начальная и конечная точки). Точка, в которой график нарушается, - это когда вы знаете, что устранили узкое место, и вы можете посмотреть на значение этого края, чтобы получить пропускную способность. (Если я не ошибаюсь, каждая итерация занимает O (E) времени, и вам понадобится O (E) итераций, чтобы найти край узкого места, так что это алгоритм O (E ² ).

Редактировать: вы должны понимать, что наибольший путь не обязательно является самой высокой пропускной способностью: вы стремитесь максимизировать значение min({edges in path}), а не sum({edges in path}).

Answer 3

Можете ли вы настроить некоторую логику в алгоритме AllPairsShortestPaths (Floyd-Warshall)? http://www.algorithmist.com/index.php/Floyd-Warshall%27s_Algorithm

Инициализировать несвязанные ребра с отрицательной бесконечностью и вместо взятия минимума расстояний взять максимум?

Answer 4

Вы можете использовать алгоритм Дейкстры, чтобы найти единственный самый длинный путь, но, поскольку у вас есть только два центра коммутации, я не понимаю, почему вам нужно посещать каждый узел, как в Дейкстре. Больше всего нравится более оптимальный способ сделать это, такой как алгоритм ветвления и привязки.

Answer 5

Просто инвертируем веса реберТо есть, если вес ребра равен d, рассмотрите его вместо d ^ -1.Тогда делай Дейкстру как обычно.Инициализируйте все расстояния до бесконечности как обычно.

Answer 6

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