Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 17, средняя оценка - 4.82
FRick
#1

Нахождение кратчайшего пути в неорентированном графе от заданой вершины к заданной - C++

12.06.2011, 15:22. Просмотров 2528. Ответов 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

В интернете нашел алгоритм Форда-Беллмана: вот код полученой программки

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
//ГЌГіГ¦Г*Г® îòêëþ÷èòü
#include <fstream>
 
//Г’Г® Г·ГІГ® Г*ГіГ¦Г*Г®
#include <iostream>
#include <string>
#include <vector>
 
using namespace std;
 
struct rebra{//ГђГҐГЎГ°Г*
    unsigned int a; //ГЌГ*Г·Г*ëî ðåáðГ*
    unsigned int b; //ГЉГ®Г*ГҐГ¶ ðåáðГ*
    unsigned int l; //ÄëèГ*Г* ðåáðГ*   
};
 
struct ver{//ГЏГ*ðû âåðøèГ*
  unsigned int a; //ÏåðâГ*Гї âåðøèГ*Г*
  unsigned int b; //ÂòîðГ*Гї âåðøèГ*Г*
};
 
unsigned int N; //Êîëè÷åñòâî âåðøèГ* Гў äåðåâå
unsigned int M; //Êîëè÷åñòâî ГЇГ*Г° âåðøèГ*
 
 
int main()
{
 
/* Ââîä Г± ГЄГ«Г*ГўГЁГ*òóðû   
cin >> N;
rebra rebra[N-2];
 
for (int i=0; i < N-1; i++) cin >> rebra[i].a >> rebra[i].b >> rebra[i].l;
 
cin >> M;
ver ver[M-1];
 
for (int i=0; i < M; i++) cin >> ver[i].a >> ver[i].b;
*/
    
  ifstream in("text2.txt"); // in - Г§Г*ìåГ*ГЁГІГј Г*Г* Г±ГІГ*Г*Г¤Г*ðòГ*ûé ïîòîê ââîäГ*
 
    in >> N;
    rebra rebra[N-2];  
 
    for (int i=0; i < N-1; i++) in >> rebra[i].a >> rebra[i].b >> rebra[i].l;
 
    in >> M;
    ver ver[M-1];
 
    for (int i=0; i < M; i++) in >> ver[i].a >> ver[i].b;
    
  in.close(); 
  
  
////............................................................................
 
const int INF = 10000000;
 
vector<int> d (N, INF);
vector<int> p (N, -1);
vector<int> path;
 
int v=1;
int t=6;
 
//if (v > t) {int tmp=v; v=t; t=tmp;}
//for (int vv=0; vv < v+1; vv++)
//d[v] = 0;
 
d[v]=0;
 
 
 
while (1)
{
  bool any = false;
  
  for (int j=0; j < N-1; j++)
  if (d[rebra[j].a] < INF)
            if (d[rebra[j].b] > d[rebra[j].a] + rebra[j].l)
            {
            d[rebra[j].b] = d[rebra[j].a] + rebra[j].l;
            p[rebra[j].b] = rebra[j].a;
        
            any = true;
            }
    if (!any) break;
}
 
if (d[t] == INF) cout << "Net puti dly " << v << " to " << t << "." << endl;
else
{
    for (size_t cur=t; cur != -1; cur=p[cur])
    path.push_back (cur);
    reverse (path.begin(), path.end());
} 
    
cout << "ot " << v << " do " << t << " pyt' prodit cherez vershini : ";
for (int i=0; i< path.size(); i++)
if (i<path.size()-1)
        cout << path [i] << "-----";
else cout << path [i] << endl<< endl;
    
    
int sum=0; 
  for (int i=0; i < N+1; i++)
  for (int j=0; j < path.size(); j++)
  if ((rebra[i].a == path[j]) && (rebra[i].b == path[j+1])) sum=sum+rebra[i].l;
  
cout << "kratchaishee rastoynie = " << sum; 
     
cout << endl<< endl;
 
 
 
////............................................................................
  
  
    cout << N << endl;
 
    for (int i=0; i < N-1; i++) cout << rebra[i].a << ' ' << rebra[i].b << ' ' << rebra[i].l << endl;
 
    cout << M << endl;
  
    for (int i=0; i < M; i++) cout << ver[i].a << ' ' << ver[i].b << endl;
  
  
    system("Pause");
    return 0;
}

Проблема заключается в следуешем. Когда задаю началюную v и конечную t вершину:
1-6 --> все хорошо выдается ответ что путь состоит из 1-2-4-5-6 вершин и длиной 17 (7+6+3+1)
но когда я хочу узнать кратчайщий путь (6-3) 3-6 (думаю это одно и то же) у меня получается неверный ответ 10 а путь 2-4-5-6, а 3 гдето теряется...


Помогите пожалуйста, голова уже кипит...
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.06.2011, 15:22
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Нахождение кратчайшего пути в неорентированном графе от заданой вершины к заданной (C++):

Нахождение кратчайшего пути в графе, алгоритм Уоршелла - C++
Привет всем! алгоритм уоршелла, нужно найти кратчайший путь в графе. ввожу матрицу 0 1 5 1 0 2 5 2 0 работает нормально, все...

Нахождение кратчайшего пути от одной вершины графа до другой - C++
Парни помогите доделать , в общем дан граф , я представил его связи в виде матрицы смежностей #include &lt;iostream.h&gt; #include...

Поиск кратчайшего пути в графе - C++
Задача: отыскать кратчайший путь между двумя заданными вершинами в произвольном ациклическом ориентированном графе с нагруженными ребрами. ...

Восстановление кратчайшего пути в графе - C++
Есть алгоритм нахождения кратчайших путей(Флойд), а как восстановить путь как узнать через какие вершины он прошел?туплю прогаю с утра)) ...

Поиск кратчайшего пути в графе - C++
Добрый вечер! Помогите решить задание пожалуйста: написать программу, решающую задачу в соответствие с вариантом, и вывести результат...

Поиск кратчайшего пути на графе - C++
Выдает ошибку Error 1 error C4996: 'itoa': The POSIX name for this item is deprecated. Instead, use the ISO C++ conformant name: _itoa. See...

1
sandye51
программист С++
685 / 587 / 39
Регистрация: 19.12.2010
Сообщений: 2,016
12.06.2011, 22:21 #2
FRick, а что, собственно, искать, если в неориентированном связном графе без циклов между 2мя вершинами существует только 1 путь, их соединяющий. У тебя в файле "text2.txt" все ответы написаны уже
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.06.2011, 22:21
Привет! Вот еще темы с ответами:

Построить алгоритм поиска кратчайшего пути между двумя вершинами в графе - C++
Блин я уже так задолбался с этим заданием может кто нибудь поможет: Построить алгоритм поиска кратчайшего пути между двумя...

Найти все вершины графа, к которым от заданной вершины можно добраться по пути не длиннее А - C++
Найти все вершины графа, к которым от заданной вершины можно добраться по пути не длиннее А. Никаких наработок нет, к сожалению, вообще...

Нахождение кратчайшего пути - C++
Нужно сделать программу,чтоб она находила кратчайший путь от города 1 до города 2 на карте. Как реализовать в коде не знаю, помогите. ...

Нахождение кратчайшего пути, поиск с возвратом - C++
Описание проблемы: Есть матрица MxN, на матрицы есть дом школьника и школа. Школьник может двигаться в 4 направления. На прохождения 1ой...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru