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

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

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

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

24.05.2013, 11:28. Просмотров 636. Ответов 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
// deikstr.cpp : Defines the entry point for the console application.
//
 
#include "stdafx.h"
#include <limits.h>
#include <conio.h>
 
const int N = 1000; //Количество вершин
bool adj_matrix[N][N];   /*Матрица смежности: adj_matrix[i][j] == true,
если между вершинами i и j существует вершина*/
int cost [N][N]; //Веса ребер
 
//Результаты работы алгоритма
int dist[N]; //Расстояния от заданной вершины
int parent[N]; /*Из какой вершины пришли
                Служит для восстановления маршрута*/
 
//start - вершина, от которой считаем расстояния
void dijkstra(int start)
{
     // in_tree[i] == true, если для вершины i
   // уже посчитано минимальное расстояние
   bool in_tree[N] = {false};
 
   for(int i = 0; i < N; i++)
      dist[i] = INT_MAX; // машинная бесконечность,
      // т. е. любое расстояние будет меньше данного
 
   dist[start] = 0; // Начальное расстояние равно нулю
 
   int cur = start; // вершина, с которой работаем
 
   // пока есть необработанная вершина
   while(!in_tree[cur])
   {
      in_tree[cur] = true;
 
      for(int i = 0; i < N; i++)
      {
         // если между cur и i есть ребро
         if(adj_matrix[cur][i])
         {
            // считаем расстояние до вершины i:
            // расстояние до cur + вес ребра
            int d = dist[cur] + cost[cur][i];
            // если оно меньше, чем уже записанное
            if(d < dist[i])
            {
               dist[i]   = d;   // обновляем его
               parent[i] = cur; // и "родителя"
            }
         }
      }
 
      // ищем нерассмотренную вершину
      // с минимальным расстоянием
      int min_dist = INT_MAX;
      for(int i = 0; i < N; i++)
      {
         if(!in_tree[i] && dist[i] < min_dist)
         {
            cur = i;
            min_dist = dist[i];
         }
      }
   }
 
   // Теперь:
   // в dist[i] минимальное расстояние от start до i
   // в parent[i] вершина, из которой лежит оптимальный путь в i
}
 
void main()
{
    int s;
    dijkstra(s);
    getch();
}
Мне надо организовать алгоритм Дейкстры. В чем у меня ошибка?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.05.2013, 11:28
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Алгоритм Дейкстры (C++):

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

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

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

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

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

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

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

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

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

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

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


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

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

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