Как сделать поиск кратчайшего пути на графе по массиву данных?

Question

[markcpp]

Есть неориентированный граф:

Можно ли (не важно каким методом) найти кратчайшие пути х1 -> х5 на графе используя массив данных ? Где x1..x2 значения из таблицы:

А в ответе получить таблицу путей:

Comments

[Moskus]

Конечно, можно. Вы поиском пользовались, алгоритм искали?

[markcpp]

Moskus, да, конечно, алгоритмов много, а как решать с массивом данных нет. Для каждых значений делать матрицу смежности? Нельзя ли просто загрузить массив и получить ответ ?..

[Moskus]

markcpp, вы не путаете понятия, случайно? Потому что когда спрашивают про алгоритм, интересуются общим принципом решения задачи. А вот когда спрашивают про "просто загрузить" - это уже не про алгоритм, а про готовую библиотеку с какими-то дополнительными удобствами. Например, как в вашем случае, с возможностью табличного представления графа.

[markcpp]

Moskus, Я имею ввиду, что вот есть у нас алгоритм, который ищет кратчайший путь, но он считывает значения которые даны в программе или при вводе с клавиатуры, мне интересно как реализовать метод цикличной работы алгоритма с таблицей "input" и записью в таблицу "output".

Answer 1

[dmshar]

Блин, народ, вы че, уже Google пользоваться разучились или попросту лень*?
Первая-же ссылка дает богатейшую пищу для мозгов:
https://habr.com/ru/post/119158/
А если чуть-чуть напрячь мозг и прочитать то, что написанопо следующим трем-четырем ссылкам, то можно уже будет из себя представлять крутого специалиста.
Если надо "просто загрузить массив и получить ответ", то таких возможностей довольно много, вот например, один из них:
https://github.com/pmatiello/python-graph

А вообще, алгоритм поиска кратчайшего пути в графе изучается на любой специальности, хоть немного связанной с ИТ.

Answer 2

[Руслан .]

Судя по нарисованному графу, тут есть два варианта пути:
1. х1-х2-х5
2. х1-х3-х4-х5
Из этих двух нужно выбрать меньший.

Ребро х2-х3 нужно исключить, т.к. в треугольнике х1-х2-х3 всегда выгоднее выбирать одну из сторон х1-х3 или
х1-х2, чем две стороны (х1-х2 + х2-х3 или х1-х3 + х3-х2).

Зная это, простым сложением по вашей таблице легко найти ответ.