FRick
|
||||||
1 | ||||||
Нахождение кратчайшего пути в неорентированном графе от заданой вершины к заданной12.06.2011, 15:22. Показов 4373. Ответов 1
Метки нет (Все метки)
Добрый день. Вот решаю задачку о кратчайщем расстояние между двумя верщинами в неорентированном связном графе без циклов.
Заданны такие параметры. (Помещаю их в файл text2.txt) 6 -- количество вершин N 1 2 7 -- Начало, конец, длина 2 3 3 2 4 6 4 5 3 5 6 1 4 -- количество пар вершин M для которых нужно узнать короткое растояние 1 6 -- первая вершина, вторая вершина; 1 3 6 3 2 5 В интернете нашел алгоритм Форда-Беллмана: вот код полученой программки
Проблема заключается в следуешем. Когда задаю началюную v и конечную t вершину: 1-6 --> все хорошо выдается ответ что путь состоит из 1-2-4-5-6 вершин и длиной 17 (7+6+3+1) но когда я хочу узнать кратчайщий путь (6-3) 3-6 (думаю это одно и то же) у меня получается неверный ответ 10 а путь 2-4-5-6, а 3 гдето теряется... Помогите пожалуйста, голова уже кипит... |
12.06.2011, 15:22 | |
Ответы с готовыми решениями:
1
Нахождение кратчайшего пути в графе Нахождение кратчайшего расстояния на графе с восстановлением пути Нахождение кратчайшего пути в графе, алгоритм Уоршелла Нахождение кратчайшего пути в графе (алгоритм Дейкстры) |
программист С++
860 / 600 / 147
Регистрация: 19.12.2010
Сообщений: 2,014
|
|
12.06.2011, 22:21 | 2 |
FRick, а что, собственно, искать, если в неориентированном связном графе без циклов между 2мя вершинами существует только 1 путь, их соединяющий. У тебя в файле "text2.txt" все ответы написаны уже
0
|
12.06.2011, 22:21 | |
12.06.2011, 22:21 | |
Помогаю со студенческими работами здесь
2
Нахождение кратчайшего пути от одной вершины графа до другой Нахождение кратчайшего пути на взвешенном графе методом ветвей и границ Описать алгоритм поиска кратчайшего пути от произвольной вершины к заданной Нахождение длины кратчайшего пути от одной вершины-источника ко всем остальным вершинам графа Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |