Темой исследования является проблема прокладки безопасного маршрута судна с учетом гидрометеорологической обстановки в районе его следования. Решение задачи предлагается с использованием теории графов. Кратчайшим маршрутом при океанском переходе является дуга большого круга, вокруг которой строится граф. Узлы графа отстоят друг от друга на расстоянии 12-часового перехода судна. Для узлов графа определяется текущая и прогностическая гидрометеорологическая информация о ветре, волнении и поверхностном течении. Для решения этой задачи предлагается использовать модифицированный алгоритм A* (A-Star). В качестве эвристической функции используется не расстояние, а кратчайшее время прохождения маршрута с учетом потерь или приращения скорости из-за влияния гидрометеорологических факторов на каждом отрезке пути между соседними вершинами графа. Предлагаемый алгоритм обладает высокой скоростью нахождения оптимального пути. Проведено компьютерное моделирование, иллюстрирующее результат работы предлагаемого модифицированного алгоритма. Полученные результаты показывают возможность значительной экономии времени при плавании по оптимальному маршруту по сравнению с плаванием по дуге большого круга. Предложенный метод может быть использован для создания систем автоматизированной прокладки оптимальных маршрутов с учетом меняющихся условий окружающей среды.