2

Есть матрица смежности вершин графа. Нужно найти кратчайший путь (не расстояние) от вершины 1 до вершины 17. Как реализовать алгоритм с использованием библиотеки boost (или любой другой. Критерий - минимум кода)? Изначально граф задан вот так:

const double graph [17][17]{
    {0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0},
    {0,0,0,0,5,5,5,5,0,0,0,0,0,0,0,0,0},
    {0,0,0,0,5,5,5,5,0,0,0,0,0,0,0,0,0},
    {0,0,0,0,8,8,8,8,0,0,0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0,0,3,3,2,2,0,0,0,0,0},
    {0,0,0,0,0,0,0,0,3,2,2,3,0,0,0,0,0},
    {0,0,0,0,0,0,0,0,1,1,2,2,0,0,0,0,0},
    {0,0,0,0,0,0,0,0,2,1,1,2,0,0,0,0,0},
    {0,0,0,0,0,0,0,0,0,0,0,0,3,0,0,0,0},
    {0,0,0,0,0,0,0,0,0,0,0,0,0,3,0,0,0},
    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,3,0,0},
    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,3,0},
    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}};

Изображение графа без указания цены ребер

1 ответ 1

1

http://www.boost.org/doc/libs/1_58_0/libs/graph/doc/dijkstra_shortest_paths.html вот boost. А вообще простейшую версию можно и самостоятельно сделать - волной пройти по всем вершинам (рекурсивный метод с 10 строчками кода), а чтобы путь восстановить - пройти в обратном направлении по наименьшим "ценам" и вершины в стек складывать (еще строк 10). Тогда в стеке окажется кратчайший путь.

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.