ЗАДАЧА ВЫБОРА КРАТЧАЙШЕГО ПУТИ
Ключевые слова:
связный неориентированный граф, выбор кратчайшего пути, пакет символьной математики Maple, алгоритм Дейкстры.
Аннотация
В практических приложениях большое значение имеет задача о нахождении кратчайшего пути между двумя вершинами связного неориентированного графа, к которой сводятся многие задачи выбора наиболее экономичного маршрута, многие задачи выбора наиболее экономичного способа перевода динамической системы из одного состояния в другое и т.д. Был разработан ряд методов решения подобных задач, и очень часто методы, основанные на теории графов, оказываются наименее трудоемкими.
Алгоритм решения данной задачи рассмотрен на конкретном примере, причем графические построения и использование алгоритма Дейкстры выполнены с использованием пакета символьной математики Maple.
