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

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

Войти
Регистрация
Восстановить пароль
 
eternalfame
0 / 0 / 0
Регистрация: 24.03.2011
Сообщений: 7
#1

Алгоритм Дейкстры(нерабочий) - C++

31.03.2011, 18:24. Просмотров 365. Ответов 0
Метки нет (Все метки)

Написал программу по нахождению кратчайшего пути алгоритмом Дейкстры. С простыми примерами программа справляется, но, к примеру, если где-то начиная со второй вершины происходит разветвление, то программа уходит в бесконечный цикл. Суть проблемы вижу - не все элементы матрицы зануляются. Но как сделать программу работоспособной, не знаю) помогите советом...

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
#include<stdio.h>
#include<conio.h>
#include<iostream.h>
#include<sstream.h>
#include<string.h>
 
void null(int n,int arr[20][20])
{
  for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
      arr[i][j]=0;
}
 
void input(int n,int arr[20][20])
{
  printf ("INPUT YOUR ARR:\n");
  for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
      scanf ("%d",&arr[i][j]);
}
 
int proverka(int n,int arr[20][20])
{
  int r=0;
  for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
      {if (arr[i][j]!=arr[j][i])
      r=1;}
  return r;
}
 
void Dxtr(int n,int W,int a,int b,int arr[20][20],int wgt[10],int k,string ms[10])
{
  int j=(a-1);
  int min1,min2;
  ostringstream os;
  do {
  for(int i=0;i<n;i++)
  {
    if (arr[i][j]!=0)
    {
      min1=arr[i][j];
      min2=i+1;
    }
  }
 for(int i=0;i<n;i++)
    if ((arr[i][j]<min1)&&(arr[i][j]!=0))
    {
      min1=arr[i][j];
      min2=i+1;
    }
  W+=arr[min2-1][j];
  if (min2-1==j)
  min2=b;
  os<<(j+1)<<'-'<<(min2)<<' ';
  arr[min2-1][j]=0;
  arr[j][min2-1]=0;
  j=(min2-1);
  }
  while (j!=b-1);
  wgt[k]=W;
  ms[k] = os.str();
  cout << ' ' << ms[k] << ' ' << endl;
}
 
void main()
{
  int n,AdG[20][20];
  printf ("INPUT ARR SIZE = ");
  scanf ("%d",&n);
  error:
  null(n, AdG);
  input(n, AdG);
  proverka(n, AdG);
  if (proverka(n, AdG)==1)
  {
    printf ("ERROR! THIS IS ORGRAPH, NOT GRAPH!\n");
    goto error;
  }
  int bgn,end;
  printf ("\nINPUT START AND END VERTEX = ");
  scanf ("%d %d",&bgn,&end);
  int W=0;
  int Weight[10];
  string marsh[10];
  int k=0;
  int stop;
  do
  {
    goo:
    Dxtr(n,W,bgn,end,AdG,Weight,k,marsh);
    printf ("Weight = %d\n\n",Weight[k]);
    k++;
    for(int p=0;p<n;p++)
      {
        {if(AdG[p][bgn-1]!=0)
        {stop=0; goto goo;}
        else
        continue;   } }
  }
  while (stop!=0);
  int minW=Weight[0];
  int minM=0;
  for (int i=0;i<=k;i++)
   { if ((Weight[i]<minW)&&(Weight[i]!=0))
   { minW=Weight[i]; minM=i; }   }
  char* chr=(char*)marsh[minM].c_str();
  printf ("\n\t\t\t!!WEIGHT = %d!!\n",minW);
  printf ("\n\t\t\t!!PATH =  %s!!\n",strrev(chr));
  getch();
}
Добавлено через 2 минуты
Граф задается весовой матрицей смежности
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
31.03.2011, 18:24
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Алгоритм Дейкстры(нерабочий) (C++):

Алгоритм Дейкстры - C++
Как на С++ в консольном приложении описать алгоритм Дейкстры?

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

Алгоритм Дейкстры - C++
Помогите найти ошибку плз. Первый шаг алгоритма выполняет правильно,а дальше-нет. #include&lt;iostream&gt; #include&lt;fstream&gt; ...

Алгоритм Дейкстры - C++
Написал программу, проверил код, в MVS6 С++ компилируется без ошибок. Но вот не задача, программа рушиться(не выполняется) при количестве...

Алгоритм Дейкстры - C++
Добрый день, помогите пож-та решить задачи на с++. Нашел решение (расписаны все алгоритмы, процедуры подсчета и т. д.), но сложность...

Алгоритм Дейкстры - C++
Ребятушки, помогите, пожалуйста. Нужна реализация алгоритма дейкстры на паскале, а именно вот этого кода const int INF = 1000000000; ...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
31.03.2011, 18:24
Привет! Вот еще темы с ответами:

Алгоритм Дейкстры - C++
Что-то у меня Дейкстра не работает... прошу помощи у вас... Сам уже часа 1.5 сижу и не могу найти ошибку...#include &lt;iostream&gt; #include...

Алгоритм Дейкстры - C++
Пытаюсь сейчас его понять, как я понял сперва надо оставить матрицу смежности, и все возможные связи между вершинами заполнить их длинами,...

Алгоритм Дейкстры - C++
День добрый! Есть игровое поле M*M. Количесво графов - N. Есть матрица смежности этого игрового поля. Получить элемент матрицы можно...

Алгоритм Дейкстры С++ - C++
Реализовать алгоритм поиска кратчайшего пути. Алгоритм Дейкстры. Представление графа – матрица смежности. как можно после того как...


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

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

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