Форум программистов, компьютерный форум CyberForum.ru

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 17, средняя оценка - 4.82
FRick
Сообщений: n/a
12.06.2011, 15:22     Нахождение кратчайшего пути в неорентированном графе от заданой вершины к заданной #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++ Построить алгоритм поиска кратчайшего пути между двумя вершинами в графе
Восстановление кратчайшего пути в графе C++
Нахождение кратчайшего пути в графе, алгоритм Уоршелла C++
C++ Нахождение кратчайшего пути, поиск с возвратом
C++ Нахождение кратчайшего пути
Найти все вершины графа, к которым от заданной вершины можно добраться по пути не длиннее А C++
Поиск кратчайшего пути на графе C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
sandye51
программист С++
 Аватар для sandye51
677 / 579 / 39
Регистрация: 19.12.2010
Сообщений: 2,016
12.06.2011, 22:21     Нахождение кратчайшего пути в неорентированном графе от заданой вершины к заданной #2
FRick, а что, собственно, искать, если в неориентированном связном графе без циклов между 2мя вершинами существует только 1 путь, их соединяющий. У тебя в файле "text2.txt" все ответы написаны уже
Yandex
Объявления
12.06.2011, 22:21     Нахождение кратчайшего пути в неорентированном графе от заданой вершины к заданной
Ответ Создать тему
Опции темы

Текущее время: 00:37. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru