2024
2023
2022
2021
2020
2019
2018
2017
Задание
(0.3) Дан ориентированный граф: V={s, a, b, c, d, f, g, e}, E={sa:1, cs:3, sf:2, fg:1, gc:2, ad:2, ab:4, be:2, dc:-1, de:-3, ge:5}. Найти кратчайший путь из s в e.
digraph {
rankdir=lr
s->a [label="1"]
c->s [label="3"]
s->f [label="2"]
f->g [label="1"]
g->c [label="2"]
a->d [label="2"]
a->b [label="4"]
b->e [label="2"]
d->c [label="-1"]
d->e [label="-3"]
g->e [label="5"]
}- (1) Написать программу, реализующую алгоритм Беллмана-Форда для поиска кратчайшего пути в ориентированном графе.
- (0.5) Найти максимальный поток в сети:
digraph {
rankdir=lr
S->a [label="5"]
S->d [label="4"]
S->c [label="2"]
a->b [label="1"]
a->d [label="3"]
b->T [label="2"]
c->d [label="3"]
d->b [label="2"]
d->T [label="8"]
}