смерть Дейкстры
Aug. 7th, 2002 08:54 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
avvaУмер Дейкстра, один из самых уважаемых специалистов в области дизайна языков программирования. Один из авторов Алгола. Автор знаменитой статьи Goto Statement Considered Harmful, и многих других знаменитых и менее знаменитых статей. Автор алгоритма Дейкстры: .
Пусть у нас есть граф, состоящий из конечного количества точек-вершин и рёбер между ними, причём рёбра направленные (т.е. можно двигаться по ним только в одном направлении) и каждое ребро - какой-то положительной длины, длины вообще говоря разные. При помощи алгоритма Дейкстры мы находим длину миминального маршрута от некоторой начальной вершины x0 до любой другой вершины графа.
В процессе выполнения алгоритма будем хранить множество вершин S, содержащее вершины, для которых минимальное расстояние от x0 уже найдено. V обозначает множество всех вершин. Будем также хранить массив Shortest(x), для каждой вершины x хранящий текущее значение минимального расстояния от x0. Curr - переменная, хранящая рассматриваемую в данный момент вершину. Length(x,y) означает длину ребра из x в y.
Алгоритм:
1. S = {x0}, Shortest(x0) = 0, Shortest(x) = бесконечность для всех остальных вершин x, Curr = x0.
2. Для каждой вершины x вне S (т.е. для всех вершин в V\S), если есть ребро из Curr в x, и если Shortest(Curr) + Length(Curr,x) < Shortest(x), то заменим Shortest(x) = Shortest(Curr) + Length(Curr,x).
Иными словами, если текущая вершина позволяет добраться до какой-то вершины вне S быстрее, чем нам до сих пор было известно для этой вершины, то подправляем наше значение минимального расстояния до этой вершины с учётом этого.
3. Из всех вершин вне S выбираем какую-то с минимальным значением Shortest(x) и добавляем в S, а также назначаем эту вершину Curr (текущей).
4. Если ещё остались вершины вне S, идём к пункту 2; если нет, заканчиваем работу, и тогда для каждой вершины x Shortest(x) содержит минимальное расстояние от x0 до x.
В основном, подозреваю, студенты в наши дни знают его имя по этому алгоритму, который они проходят на том или ином курсе.
Автор целой эпохи, как ни банально это звучит.
R.I.P.
Пусть у нас есть граф, состоящий из конечного количества точек-вершин и рёбер между ними, причём рёбра направленные (т.е. можно двигаться по ним только в одном направлении) и каждое ребро - какой-то положительной длины, длины вообще говоря разные. При помощи алгоритма Дейкстры мы находим длину миминального маршрута от некоторой начальной вершины x0 до любой другой вершины графа.
В процессе выполнения алгоритма будем хранить множество вершин S, содержащее вершины, для которых минимальное расстояние от x0 уже найдено. V обозначает множество всех вершин. Будем также хранить массив Shortest(x), для каждой вершины x хранящий текущее значение минимального расстояния от x0. Curr - переменная, хранящая рассматриваемую в данный момент вершину. Length(x,y) означает длину ребра из x в y.
Алгоритм:
1. S = {x0}, Shortest(x0) = 0, Shortest(x) = бесконечность для всех остальных вершин x, Curr = x0.
2. Для каждой вершины x вне S (т.е. для всех вершин в V\S), если есть ребро из Curr в x, и если Shortest(Curr) + Length(Curr,x) < Shortest(x), то заменим Shortest(x) = Shortest(Curr) + Length(Curr,x).
Иными словами, если текущая вершина позволяет добраться до какой-то вершины вне S быстрее, чем нам до сих пор было известно для этой вершины, то подправляем наше значение минимального расстояния до этой вершины с учётом этого.
3. Из всех вершин вне S выбираем какую-то с минимальным значением Shortest(x) и добавляем в S, а также назначаем эту вершину Curr (текущей).
4. Если ещё остались вершины вне S, идём к пункту 2; если нет, заканчиваем работу, и тогда для каждой вершины x Shortest(x) содержит минимальное расстояние от x0 до x.
В основном, подозреваю, студенты в наши дни знают его имя по этому алгоритму, который они проходят на том или ином курсе.
Автор целой эпохи, как ни банально это звучит.
R.I.P.
