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

алгоритм Дейкстры - C++

Восстановить пароль Регистрация
 
Despot777
1 / 1 / 0
Регистрация: 14.09.2013
Сообщений: 118
20.11.2013, 20:19     алгоритм Дейкстры #1
Разработать и отладить программу поиска кратчайшего пути в неориентированном взвешенном графе (алгоритм Дейкстры).
Вот мой код. Не пойму почему он выводит кривой результат
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
#include <iostream>
#include <conio.h>
#pragma hdrstop
#pragma argsused
#define graph 6 
using namespace std;
 
int main(int argc, char* argv[])
{setlocale(LC_ALL, ".1251");
   int infinity=1000;
   int v;                     
   int p= graph;             
   int a[graph][graph]={0,3,5,5,0,0,  
                        3,0,2,0,0,0,
                        5,2,0,0,0,1,
                        5,0,0,0,6,0,
                        0,0,0,6,0,2,
                        0,0,1,0,2,0};
 
   int s;                   
   int g;                   
   cout<<"Ââåäèòå Г*Г*Г·Г*ëüГ*ГіГѕ òî÷êó s: ";     
   cin>>s;
   cout<<"Ââåäèòå ГЄГ®Г*ГҐГ·Г*ГіГѕ òî÷êó g: ";
   cin>>g;
   int x[graph]; 
   int t[graph];  
   int h[graph];  
   int u;           
   for (u=0;u<p;u++)
   {
      t[u]=infinity; 
    
      x[u]=0;        
   }
   h[s]=0; 
   t[s]=0; 
   x[s]=1; 
   v=s;    
   
   while(1)
   {
      
      for(u=0;u<p;u++)
      {
         if(a[v][u]==0)continue; 
         if(x[u]==0 && t[u]>t[v]+a[v][u]) 
    
         {
            t[u]=t[v]+a[v][u];  
            h[u]=v; 
         }
      }
 
      
      int w=infinity;  
      v=-1;            
      for(u=0;u<p;u++) 
      {
         if(x[u]==0 && t[u]<w) 
         {
            v=u; 
            w=t[u];
         }
      }
      if(v==-1)
      {
         cout<<"ГЌГҐГІ ГЇГіГІГЁ ГЁГ§ âåðøèГ*Г» "<<s<<" Гў âåðøèГ*Гі "<<g<<"."<<endl;
         break;
      }
      if(v==g) 
      {        
         cout<<"ГЉГ°Г*Г·Г*éøèé ГЇГіГІГј ГЁГ§ âåðøèГ*Г» "<<s<<" Гў âåðøèГ*Гі "<<g<<":";
       u=g;
       while(u!=s)
         {
            cout<<" "<<u;
            u=h[u];
         }
         cout<<" "<<s<<". ÄëèГ*Г* ГЇГіГІГЁ - "<<t[g];
       break;
      }
      x[v]=1;
   }
   getch();
   return 0;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
20.11.2013, 20:19     алгоритм Дейкстры
Посмотрите здесь:

Алгоритм Дейкстры C++
Алгоритм Дейкстры C++
C++ Алгоритм Дейкстры
C++ Алгоритм Дейкстры
Алгоритм Дейкстры C++
Алгоритм Дейкстры C++
Алгоритм Дейкстры C++
C++ Алгоритм Дейкстры

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

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