Я сделал график, используя хеш-таблицу вместо матрицы смежности. Мне очень трудно реализовать алгоритм кратчайшего пути с тем, как я его настроил.
Я попытался пройтись по краям начального узла, затем выбрать кратчайший путь и затем проверить все его дочерние элементы при обновлении его пред. Затем я рекурсивно вызываю функцию на узле с кратчайшим путем, обновляю его prev, если это более короткий путь, и сканирую его дочерние элементы. кажется, ничего не работает.
Мне интересно, нужно ли мне просто настроить его с помощью векторов. Я хотел сделать это таким образом, потому что это экономит память.
/// это то, что я пытался заставить работать
// вывод на печать (все в переточах - это стоимость ребер)
Я | Подключенные узлы
0 | -> 1 (9), -> 2 (10), -> 3 (4), -> NULL
1 | -> 0 (9), -> 4 (7), -> 5 (20), -> NULL
2 | -> 0 (10), -> 6 (3), -> NULL
3 | -> 0 (4), -> 7 (1), -> NULL
4 | -> 1 (7), -> 7 (8), -> NULL
5 | -> 1 (20), -> 7 (8), -> NULL
6 | -> 2 (3), -> 7 (99), -> NULL
7 | -> 3 (1), -> 4 (8), -> 5 (8), -> 6 (99), -> NULL