Учебная страница курса биоинформатики,
год поступления 2011

Семестры Студенты Преподаватели

• 2024
• 2023
• 2022
• 2021
• 2020
• 2019
• 2018
• 2017

• ...

Графы: поиск кратчайшего пути в графе, алгоритм Дейкстры, алгоритм Беллмана-Форда

1. (0.5) Дан неориентированный граф: V={s, a, b, c, f, d, e}, E={sa:1, sc:2, ac:3, ab:3, ad:2, cd:4, cf:1, fd:1, de:1, bd:2, de:1, be:1}. Найти кратчайший путь из s в e.

2. (0.5) Дан ориентированный граф: 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.

3. (1.5) Написать программу, реализующую алгоритм Беллмана-Форда для поиска кратчайшего пути в ориентированном графе.
4. (2) Написать программу, реализующую алгоритм Дейкстры для поиска кратчайшего пути в графе.

Визуализированные графы

graph {
rankdir=lr
s--a [label="1"]
s--c [label="2"]
a--c [label="3"]
a--b [label="3"]
a--d [label="2"]
c--d [label="4"]
c--f [label="1"]
f--d [label="1"]
d--e [label="1"]
b--d [label="2"]
d--e [label="1"]
b--e [label="1"]
}

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"]
}