Почитал ветку от начала до конца. Возникли две мысли.
1. В начале дискуссии участники требовали реальные примеры использования цикла Дейкстры. Реальный пример у меня есть. Писал как-то я парсер DNS-запросов на Си. Формат его довольно мудрёный и мне не сразу приходила мысль, как сформулировать алгоритм. Записал его через эмулированный цикл Дейкстры (while (true) { if (…) else if (…) else break; }) — сразу стала понятна логика. Затем чутка оптимизировал. Вот что получилось.
Код:
while (offset < data_length && data[offset] != '\0')
{
if ((data[offset] & 0xC0) == 0)
{
uint8_t length = (uint8_t) data[offset];
++offset;
if (offset + length > data_length ||
dnp + length + 1 > DNS_MAX_DOMAIN_NAME)
return false;
memcpy(domain_name + dnp, data + offset, length);
offset += length;
dnp += length;
domain_name[dnp] = '.';
++dnp;
}
else if ((data[offset] & 0xC0) == 0xC0)
{
// Компрессия: если установлены оба старших бита,
// то пара октетов, состоящая из текущего байта и следующего
// образует смещение остатка имени ранее в этом пакете.
size_t new_offset = ntohs(*(const uint16_t*)(data + offset)) & ~0xC000;
if (new_offset >= *data_offset)
return false;
if (end_of_first_segment == 0)
end_of_first_segment = offset + sizeof(uint16_t);
offset = new_offset;
}
else
break;
}
Вывод: если некий алгоритм сложный, то сначала стоит попробовать сформулировать его через алгоритм Дейкстры, а потом оптимизировать.
2. Утверждается, что первый язык, реализующий цикл Дейкстры — это Оберон-07. Поправка: первый императивный язык. Ведь в языках функционального программирования (особенно pattern-matching-языки типа Хаскеля, Рефала или Эрланга) цикл Дейкстры реализуется просто и естественно. Если цикл WHILE это func f(x) = if c(x) then f(x’) else y, то ЦД — func f(x) = if c1(x) then f(x') elif c2(x) then f(x'') … else y. Ведь конструкции типа if-elif-else есть практически во всех языках программирования.