Пусть требуется перевезти груз из города A в город В. Сеть дорог, связывающих эти города, задана в виде графа. Вершинам графа поставлены в соответствие города, а дугам - транспортные магистрали. Стоимость перевозки груза из города
в город
проставлена над соответствующими дугами графа. Необходимо найти маршрут, связывающий города A и В, для которого суммарные затраты на перевозку груза будут наименьшими.