Есть задача: найти такой маршрут из начальной вершины в конечную, чтобы минимальное значение веса ребра на этом маршруте было наибольшим. Веса ребер неотрицательны, граф неориентированный.

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

Предлагался "алгоритм": 1)найти все возможные пути из А в В и 2)выбрать путь максимальной пропускной способности. Но это, если я что-то в чем-то понимаю, поиск в глубину. Хотелось бы быстрее.

Еще преподаватель на полном серьезе излагал метод: заменить веса обратными величинами и искать маршрут минимального веса. Это не работает, сразу понятно, но что-то в этом есть. Пока мысль ускользает.

Поделитесь, пожалуйста, идеями.

Здравствуйте, functional, Вы писали:

Ищи на том же гугле "Потоки в сетях", "Максимальный поток", "алгоритм Форда-Фалкерсона"

Здравствуйте, functional, Вы писали:

F>Поделитесь, пожалуйста, идеями.
Эх, блин. Темный я человек. Знаю, как решить задачу за O(N^3). Это, наверное, слишком медленно. Хотя и очевидно

Здравствуйте, Sinclair, Вы писали:

S>Знаю, как решить задачу за O(N^3). Это, наверное, слишком медленно.

Пусть медленно. Если не тупым перебором, все равно интересно. Может быть, получится "дожать".

S>Хотя и очевидно

Для кого как — колись, что придумал. Я затем вопрос и задал, чтоб узнать нечто, очевидное для всезнающего A.

F>Поделитесь, пожалуйста, идеями.

Помодифицируй алгоритм Флойда. Замени сумму на минимум

Здравствуйте, DeaTH FaNG, Вы писали:
DF>Помодифицируй алгоритм Флойда. Замени сумму на минимум

Жалею, что сам не додумался.
Для этого, наверное, нужно было лучше понимать алгоритм Флойда.

Если я правильно понял, еще и min заменяется на max. Формула для пересчета матрицы из

dijm+1=min{dijm, di(m+1)m + d(m+1)jm}

превращается в

dijm+1=max{dijm, min(di(m+1)m, d(m+1)jm)}

Благодарю за помощь.

Здравствуйте, functional, Вы писали:

F>Жалею, что сам не додумался.
F>Для этого, наверное, нужно было лучше понимать алгоритм Флойда.

Понимать алгоритм Флойда, конечно, нужно , но для поставленной задачи
он совершенно не оптимален ни по времени, ни по памяти.

Задачу можно решить за O(E*log E) (E -- число ребер в графе).
Для этого отсортируем все ребра по весам (O(E*log E)), после чего
ответ найдем бинарным поиском. Фиксировав границу A, выкининем
все ребра веса меньше A и проверим (поиском в ширину, например),
есть ли путь между заданной парой вершин (O(E) на каждый поиск,
O(log E) итераций).

Это решение можно немного модифицировать, просто добавляя
ребра поочереди и проверяя связность с помощью disjoint set-ов.
В данной задаче быстрее не будет, но в некоторых других полезно.

Здравствуйте, functional, Вы писали:

F>Для кого как — колись, что придумал. Я затем вопрос и задал, чтоб узнать нечто, очевидное для всезнающего A.
см. ответ Death Fang.