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

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

Восстановить пароль Регистрация
Другие темы раздела
C++ Массив http://www.cyberforum.ru/cpp-beginners/thread318283.html
Помогите разобраться. Только начал читать про указатели и решил написать простенькую программку :) Она считает кол-во прописных букв и записывает эти буквы в массив. Насчет счетчика всё ясно, но вот как записывать буквы в массив не разобрался. GNU nano 2.2.6 Файл: p209E12.cpp #include <cctype> #include <iostream> using namespace std; main() {
C++ исправить код программы #include<iostream.h> #include<conio.h> #include<stdlib.h> #include<string.h> #include<iomanip.h> float f( float, float, float, float); float pr_chet( float *mas, int k); float sum_f( float *mas,int k); void Vivod_mas(float a,int k); http://www.cyberforum.ru/cpp-beginners/thread318270.html
Дискриминант C++
Даны числа A,B,C (Число А не равно нулю) Расмотрев дискриминант D=b^2-4*a*c проверить истинность высказывания ax^2+bx+c=0 имеет вещественные корни. Если можно попроще обьяснить я только начал всем спасибо заранее. пример А=2.68, В=0.93, с=-8.62 ---Истина
C++ HANDLE файла зная путь к нему
Привет всем. Подскажите с помощью какой функции можно получить HANDLE файла, при наличии полного пути к єтому фалу?
C++ шифрирование. http://www.cyberforum.ru/cpp-beginners/thread318258.html
Не могу сделать так чтобы при запуске программы сначало стоял выбор зашифровать текст или расшифровать. Помогите, курсовую сдать надо. #include <iostream.h> #include <stdio.h> #include <string.h> #include <stdlib.h> #include <fstream.h> #include <math.h>
C++ напишите программу!!! тема "работа с символьными данными"!!! Прочитать из файла строку символов. Удалить в этой строке каждый символ * и повторить каждый символ, отличный от *. Новую строку не создавать. Вывести исходную и преобразованную строки. подробнее

Показать сообщение отдельно
FRick
Сообщений: n/a
12.06.2011, 15:22     Нахождение кратчайшего пути в неорентированном графе от заданой вершины к заданной
Добрый день. Вот решаю задачку о кратчайщем расстояние между двумя верщинами в неорентированном связном графе без циклов.
Заданны такие параметры. (Помещаю их в файл 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 гдето теряется...


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