Введение

Каждый человек ежедневно, не всегда осознавая это, решает проблему: как получить наибольший эффект, обладая ограниченными средствами. Наши средства и ресурсы всегда ограничены. Не трудно выиграть сражение, имея армию в 10 раз большую, чем у противника. Но такой избыток ресурсов бывает не всегда. Чтобы достичь наибольшего эффекта, имея ограниченные средства, надо составить план, или программу действий. Теория графов рассматривает широкий круг задач с единой математической моделью, она находится сейчас в самом расцвете. Обычно её относят к топологии (потому что во многих случаях рассматриваются лишь топологические свойства графов), однако она пересекается со многими разделами теории множеств, комбинаторной математики, алгебры, геометрии, теории матриц, теории игр, математической логики и многих других математических дисциплин.

Голландский ученый Эдсгер Вайб Дейкстра (1930-2002) внес большой вклад в развитие динамического программирования и теорию графов. Известность Дейкстре принесли его работы в области применения математической логики при разработке компьютерных программ. Рассказывать об этом человеке можно очень долго и много. Можно перечислять научные регалии, звания и степени, бесконечно повторять слова "неоценимый вклад" и "основоположник". Он являлся одним из главных разработчиков языка ALGOL. Также ему принадлежит идея применения "семафоров" для синхронизации процессов в многозадачных системах и алгоритм нахождения кратчайшего пути на ориентированном графе с неотрицательными весами рёбер, известный как Алгоритм Дейкстры. В 1972 году за свой вклад в развитие информационных технологий Дейкстра был удостоен премии Тьюринга, которую называют аналогом Нобелевской премии в области компьютеров.

Здесь сразу уместно будет привести несколько фрагментов из воспоминаний Дейкстры. Во-первых, алгоритм этот создавался не из простого любопытства, а для решения вполне конкретной задачи, а именно, - минимизации длины проводников на аналоге "материнской платы" нового разрабатываемого командой компьютера X1, так что лавровый венок создателя первой "утилиты всех времен и народов" класса CAD-CAE Дейкстре можно присваивать смело. А вот "во-вторых" лучше сказать словами самого Дейкстры: "На много лет и в широких кругах алгоритм поиска кратчайшего пути был основным источником моей славы, что мне всегда казалось странным - ведь он был создан даже без карандаша и бумаги, за чашкой кофе на солнечной террасе кафе в Амстердаме".