Изменения

Теория графов:Тикеты

1648 байт добавлено, 02:39, 29 сентября 2018

→‎5. Кратчайшие пути в графах

== 5. Кратчайшие пути в графах ==

# [[Обход в ширину]]

## исправить речевые ошибки в описании

## поправить тех

## 0-1 bfs переписать

## нормально сформулировать доказательство 1ого утверждения

## поправить псевдокод ("in", "=="(хотя уже есть <tex>\ne</tex>), "Q = <tex>\varnothing</tex>")

## добавить "см. также"

# [[Алгоритм Форда-Беллмана]]

## поправить тех для чисел

## из s достижимы циклы отрицательного веса <tex>\nRightarrow</tex> не существует кратчайших путей

## весь конспект бессвязный - не ясно что к чему и как относится. Нормально структурировать

## сделать доказательство первой леммы более содержательным

## пункт "Псевдокод" - бред почти полностью

## иногда w(x, y), иногда w(xy) - исправить; обычно написано в неверном порядке

## систематизировать комментарии в псевдокоде (добавить, сделать содержательными)

## добавить "см. также"

# [[Алгоритм Дейкстры]] 0.5

## в таблице из оценки сложности поиск минимума не правильно указан для двоичной кучи и для фибоначчиевой кучи

## добавить "см. также"

# [[Алгоритм Флойда]]

## поправить нерабочий тех

## переписать, чтобы индексация d была везде через "[]"

## комментарии в псевдокоде несодержательны

# [[Алгоритм Джонсона]]

# [[Алгоритм Левита]]

# [[Алгоритм A*]]

## теорема доказана не полностью

# [[Алгоритм D*]]

## добавить "см. также"

# [[Эвристики для поиска кратчайших путей]]

47

правок