Построение взвешенного графа по весу осей X и Y и нахождение кратчайшего пути(Путей)? Добрый день дорогие друзья. Подскажите пожалуйста, как построить граф, когда известный веса осей X и Y. Веса:Веса по оси Х(18953 85973 17318 89738 15973 81687) и Веса по оси Y(89891 15789 11537 31871 89897 89878) и надо найти:
а) превратить его во взвешенный граф с помощью персонального набора данных (в них веса горизонтальных ребер помечены буквой Х, веса вертикальных ребер – буквой Y);
б) Найти кратчайший путь (или пути) из вершины А в вершину В.
Построение взвешенного графа по весу осей X и Y и нахождение кратчайшего пути(Путей)? Добрый день дорогие друзья. Подскажите пожалуйста, как построить граф, когда известный веса осей X и Y. Веса:Веса по оси Х(18953 85973 17318 89738 15973 81687) и Веса по оси Y(89891 15789 11537 31871 89897 89878) и надо найти:
а) превратить его во взвешенный граф с помощью персонального набора данных (в них веса горизонтальных ребер помечены буквой Х, веса вертикальных ребер – буквой Y);
б) Найти кратчайший путь (или пути) из вершины А в вершину В.
а) превратить его во взвешенный граф с помощью персонального набора данных (в них веса горизонтальных ребер помечены буквой Х, веса вертикальных ребер – буквой Y);
б) Найти кратчайший путь (или пути) из вершины А в вершину В.
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки в течение 1 года
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Поможем написать учебную работу
Для начала построим взвешенный граф по данным весам осей X и Y. Вершинами графа будут точки пересечения осей X и Y, а ребрами будут соединены соседние вершины с соответствующими весами.
Таким образом, наш взвешенный граф будет иметь вид:
[
\begin{array}{|c|c|c|c|c|c|c|}
\hline
& A & B & C & D & E & F \
\hline
1 & 18953_Y & 85973_Y & 17318_Y & 89738_Y & 15973_Y & 81687_Y \
\hline
2 & 89891_X & & & & & \
\hline
3 & 15789_X & & & & & \
\hline
4 & 11537_X & & & & & \
\hline
5 & 31871_X & & & & & \
\hline
6 & 89897_X & & & & & \
\hline
7 & 89878_X & & & & & \
\hline
\end{array}
]
Теперь найдем кратчайший путь из вершины A в вершину B. Для этого можно воспользоваться алгоритмом Дейкстры или алгоритмом Флойда-Уоршалла.
После выполнения выбранного алгоритма получится кратчайший путь (или пути) из вершины A в вершину B.
Надеюсь, это поможет вам решить вашу задачу. Если у вас возникнут дополнительные вопросы, не стесняйтесь спрашивать.