Задача на максимальный поток в Visual Basic - VB
Формулировка задачи:
У меня есть граф, в нём 25 точек.
необходимо решить задачу на максимальный поток. выходим из Донецка, приходим в Киев.
вот как я находил это на графе меньшего размера:
а вот сам алгоритм нахождения (Форда — Фалкерсона):
1) Обнуляем все потоки. Остаточная сеть изначально совпадает с исходной сетью.
2) В остаточной сети находим любой путь из источника в сток. Если такого пути нет, останавливаемся.
3) Пускаем через найденный путь (он называется увеличивающим путём или увеличивающей цепью) максимально возможный поток:
1. На найденном пути в остаточной сети ищем ребро с минимальной пропускной способностью Cmin .
2. Для каждого ребра на найденном пути увеличиваем поток на Cmin , а в противоположном ему — уменьшаем на Cmin .
3. Модифицируем остаточную сеть. Для всех рёбер на найденном пути, а также для противоположных им рёбер, вычисляем новую пропускную способность. Если она стала ненулевой, добавляем ребро к остаточной сети, а если обнулилась, стираем его.
4) Возвращаемся на шаг 2.
я сделал только часть, обнулил все потоки, но не пойму как выбрать путь из источника в сток, и что делать после этого.
вот код:
Если у кого-то есть какие-то идеи, need your help
Спойлер
Спойлер
Листинг программы
- Private Sub Form_Load()
- Dim a()
- Dim b()
- Dim n As Integer
- Dim Min As Integer
- n = 25
- ReDim a(n, n)
- ReDim b(n, n)
- Dim l(1 To 25) As Integer
- Dim m(1 To 25) As Integer
- Dim i%, j%
- Dim s As String, st As String
- Dim phi As String
- For i = 1 To n ' îáГ*óëåГ*ГЁГҐ ГўГ±ГҐГµ Г§Г*Г*Г·ГҐГ*ГЁГ© Г¬Г*Г±Г±ГЁГўГ* Г± Г°Г*ññòîÿГ*èÿìè
- For j = 1 To n
- a(i, j) = 0
- Next j
- Next i
- a(1, 2) = 248: a(1, 5) = 337: a(1, 6) = 273
- a(2, 3) = 151: a(2, 4) = 210: a(2, 5) = 133: a(2, 6) = 141
- a(3, 4) = 70: a(3, 5) = 166
- a(4, 5) = 156: a(4, 8) = 194: a(4, 10) = 192
- a(5, 6) = 150: a(5, 7) = 172: a(5, 8) = 107
- a(6, 7) = 139
- a(7, 8) = 184
- a(8, 9) = 118: a(8, 10) = 183
- a(9, 10) = 127: a(9, 12) = 424: a(9, 14) = 341: a(9, 15) = 310: a(9, 16) = 428
- a(10, 12) = 131
- a(11, 12) = 492: a(11, 13) = 143: a(11, 14) = 186: a(11, 15) = 302: a(11, 18) = 337: a(11, 19) = 344: a(11, 20) = 449
- a(12, 16) = 137
- a(13, 14) = 297: a(13, 18) = 335: a(13, 19) = 405: a(13, 20) = 558
- a(14, 15) = 137: a(14, 18) = 361: a(14, 20) = 289
- a(15, 16) = 181: a(15, 19) = 245: a(15, 20) = 243: a(15, 21) = 301
- a(16, 17) = 63: a(16, 20) = 319
- a(17, 20) = 325: a(17, 21) = 282: a(17, 22) = 268
- a(18, 19) = 170: a(18, 23) = 187
- a(19, 20) = 186: a(19, 23) = 149: a(19, 24) = 391
- a(20, 21) = 79: a(20, 23) = 226: a(20, 24) = 245
- a(21, 22) = 388: a(21, 24) = 229
- a(22, 24) = 560
- a(23, 24) = 301: a(23, 25) = 341
- a(24, 25) = 151
- For i = 1 To n 'Г§Г*ïîëГ*ГҐГ*ГЁГҐ ñèììåòðè÷Г*îé Г·Г*Г±ГІГЁ Г¬Г*Г±Г±ГЁГўГ* Г± Г°Г*ñññòîÿГ*èÿìè
- For j = 1 To n
- If a(i, j) <> 0 Then a(j, i) = a(i, j)
- Next j
- Next i
- s = " "
- For i = 1 To n ' âûâîä Г*Г*Г·Г*ëüГ*îãî Г¬Г*Г±Г±ГЁГўГ* Г± Г°Г*ññòîÿГ*èÿìè
- For j = 1 To n
- s = s & a(i, j) & " "
- Next j
- s = s & vbCrLf
- Next i
- Label1.Caption = s
- 'îáГ*óëåГ*ГЁГҐ ГўГ±ГҐГµ ГґГЁ
- For i = 1 To n
- For j = 1 To n
- b(i, j) = 0
- Next j
- Next i
- ' âûâîä ôè
- For i = 1 To n
- For j = 1 To n
- phi = phi & b(i, j) & " "
- Next j
- phi = phi & vbCrLf
- Next i
- Label2.Caption = phi
- End Sub
Решение задачи: «Задача на максимальный поток в Visual Basic»
textual
Листинг программы
- a(1, 5) = 337
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д