Kodomo

Пользователь

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

Графы. Поиск оптимального пути

  1. (0.2) Дан граф граф1, найти оптимальный путь из S в 6.

  2. (0.5) Дан граф граф2, найти оптимальный путь из A в H.

  3. (1.0) Написать программу, осуществляющую топологическую сортировку вершин в графе.

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

  1. (0.3) Дан неориентированный граф: 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. (1.5) Написать программу, реализующую алгоритм Дейкстры для поиска кратчайшего пути в графе.

Граф из задания 1

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