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

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

Восстановить пароль Регистрация
 
Aksakov
1 / 1 / 0
Регистрация: 23.05.2013
Сообщений: 23
24.05.2013, 11:28     Алгоритм Дейкстры #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
// 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++
C++ Алгоритм Дейкстры
C++ Алгоритм Дейкстры
Алгоритм Дейкстры C++
Алгоритм Дейкстры C++
Алгоритм Дейкстры C++
C++ Алгоритм Дейкстры

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

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

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