Дискретная математика

165 Алгоритм Дейкстр ы. begin for каждой V sVdo begin d[v\.= fi(A,v)\ PUTH(v);=^; end Отметить вершину A\ while остаются неотмеченные вершины do begin м:=неотмеченную вершину с минимальным расстоянием от ^ ; Отметить вершину м; for каждой неотмеченной вершины v с условием (u,v) <еХ do begin d':= d[u\+ f^(u,v); if d*< d[v] then begin PUTH( V ):=PUTH( M), V; end end end end Цепь не крепче своего самого слабого звена. Английская ?ioooewj/a § 19. Потоки в сетях Деятельность современного обш^ества тесно связана с разного рода сетями - транспортные сети, электрические сети, сети нефтепроводов и т.д. Если различна пропускная способность элементов сети, то можно ставить вопрос о максгшизацни потоков в сетях. Например, есть сеть дорог, ведущих из Владивостока в Санкт-Петербург; известна пропускная способность каждой ветки; требуется определить максимачьный поток грузов, допустимых для заключения договора о доставке контейнеров из Японии в Европу. Сетью S (^или транспортной сетью) называется орграф, обладающий следующими свойствами: 1) существует единственная вершина vn, называемая входом или источником, в которую не заходит ни одна дуга (полустепень захода вершины vo равна нулю);