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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 33, средняя оценка - 4.91
shPavel25
 Аватар для shPavel25
6 / 6 / 0
Регистрация: 29.03.2011
Сообщений: 44
30.07.2012, 20:52     Алгоритм Дейкстры #1
Добрый день, помогите пож-та решить задачи на с++. Нашел решение (расписаны все алгоритмы, процедуры подсчета и т. д.), но сложность состоит в том, что я не понимаю строищихся структур и вообще никогда не программировал на c++.Поэтому прошу помочь собрать все воедино (чтение из файла, работа программы, запись в файл). Основная задача - считать с файла, воспользоваться функцией, вывести в файл
Дан ориентированный взвешенный граф. Требуется найти минимальные расстояния от вершины S до всех остальных вершин.
Вход:
В первой строке через пробел записаны два натуральных числа N и S (S <= N < 103), где N – число вершин графа (нумерация вершин от 1 до N). В следующих N строках записана матрица смежности графа (формат ввода смотрите в примере). Веса ребер – натуральные числа, не превосходящие 106. Если какого-либо ребра нет, то соответствующий ему элемент матрицы равен -1. На главной диагонали стоят нули. Строки матрицы соответствуют вершинам, из которых направлены ребра.
Выход:
В первых N строках выведите по одному числу –минимальному расстоянию из вершины S в соответствующую вершину. Если пути из вершины S в какую-либо вершину не существует, то в соответствующей строке выведите -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
const int INF = 1000000000;
int main() {
int n;
... чтение n ...
vector < vector < pair<int,int> > > g (n);
... чтение графа ...
int s = ...; // стартовая вершина
vector<int> d (n, INF), p (n);
d[s] = 0;
vector<char> u (n);
for (int i=0; i<n; ++i) {
int v = -1;
for (int j=0; j<n; ++j)
if (!u[j] && (v == -1 || d[j] < d[v]))
v = j;
if (d[v] == INF)
u[v] = true;
for (size_t j=0; j<g[v].size(); ++j) {
int to = g[v][j].first,
len = g[v][j].second;
if (d[v] + len < d[to]) {
d[to] = d[v] + len;
p[to] = v;
}
}
}
}
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
30.07.2012, 20:52     Алгоритм Дейкстры
Посмотрите здесь:

Алгоритм Дейкстры C++
Алгоритм Дейкстры C++
C++ Алгоритм Дейкстры
Алгоритм Дейкстры С++ C++
C++ Алгоритм Дейкстры
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
nameless
Эксперт C++
 Аватар для nameless
289 / 288 / 14
Регистрация: 16.06.2009
Сообщений: 486
30.07.2012, 21:39     Алгоритм Дейкстры #2
Сообщение было отмечено автором темы, экспертом или модератором как ответ
shPavel25, с boost::graph

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
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
 
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
 
typedef boost::adjacency_list <boost::listS, boost::vecS, boost::directedS,
   boost::no_property, boost::property <boost::edge_weight_t, int>> graph_type;
typedef boost::graph_traits <graph_type>::vertex_descriptor vertex_descriptor;
typedef boost::graph_traits <graph_type>::edge_descriptor edge_descriptor;
typedef std::pair <int, int> edge;
 
const int Number_Nodes = 6;
enum nodes { A, B, C, D, E, F };
 
int main() {
   std::string nodes_name = "ABCDEF";
   std::vector <edge> edges_array = { 
                        edge(A, B), edge(A, C), edge(A, F),
                        edge(B, C), edge(B, D), edge(C, D),
                        edge(C, F), edge(D, E), edge(E, F)
                      };
   std::vector <int> weights_array = { 7, 9, 14, 10, 15, 11, 2, 6, 9 };
   
   graph_type graph(
      edges_array.begin(),
      edges_array.end(),
      weights_array.begin(),
      Number_Nodes
   );
   
   std::vector <vertex_descriptor> p(boost::num_vertices(graph));
   std::vector <int> distance_array(boost::num_vertices(graph));
   vertex_descriptor s = boost::vertex(A, graph);
   
   boost::dijkstra_shortest_paths(
      graph,
      s, 
      boost::predecessor_map(&(*p.begin())).distance_map(&(*distance_array.begin()))
   );
   
   boost::graph_traits <graph_type>::vertex_iterator vp, vend;
   boost::tie(vp, vend) = vertices(graph);
 
   std::for_each(
      vp,
      vend,
      [&nodes_name, &distance_array](int value) {
         std::cout << "distance to " << nodes_name[value] 
                   << " equal to "   << distance_array[value] << "\n";
      }
   );
}
http://liveworkspace.org/code/b1497c...4b6aa58cf6ba93

Со считыванием проблем возникнуть не должно..
b_kasenov47
14 / 14 / 1
Регистрация: 28.07.2012
Сообщений: 57
30.07.2012, 23:57     Алгоритм Дейкстры #3
Примеры с емакса сразу палятся))) Вот переделано чуток)))
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
#include <iostream>
#include <cstdio>
 
using namespace std;
 
int g[150][150];
 
bool used[150];
 
int d[150];
 
const int inf = 1000000000;
 
int main()
{
    freopen("input.txt","r",stdin); // если файлы не нужны то эти 2 строки удалить
    freopen("output.txt","w",stdout);
    int n, s;
    cin >> n >> s;
    s--; //нумерация массивов в с++ идет с нуля
    for (int i = 0; i < n; i++)
         for (int j = 0; j < n; j++)
             cin >> g[i][j]; //считывание графа
    for (int i = 0; i < n; i++)
        d[i] = inf;
    d[s] = 0;
    for (int i = 0; i < n; i++)
        {
            int v = -1;
            for (int j = 0; j < n; j++)
                 if (!used[j])
                      if (v == -1 || d[j] < d[v])
                           v = j; //нахождение вершины с минимальной меткой
             used[v] = true;
             for (int j = 0; j < n; j++)
                  if (g[v][j] != -1 && i!=j)
                      d[j] = min(d[v] + g[v][j], d[j]);//релаклации через эту вершину
         }
    for (int i = 0; i < n; i++)
         if (d[i] == inf)
             cout << -1 << ' ';
          else
             cout << d[i] << ' ';//вывод ответа
return 0;
}
shPavel25
 Аватар для shPavel25
6 / 6 / 0
Регистрация: 29.03.2011
Сообщений: 44
31.07.2012, 00:57  [ТС]     Алгоритм Дейкстры #4
Спасибо
bubliq
 Аватар для bubliq
0 / 0 / 0
Регистрация: 10.03.2013
Сообщений: 17
09.07.2015, 17:09     Алгоритм Дейкстры #5
ваш код не работает
forze96
0 / 0 / 0
Регистрация: 12.11.2014
Сообщений: 11
20.11.2015, 17:54     Алгоритм Дейкстры #6
C
1
min(d[v] + g[v][j], d[j]);
Понимаю, что тема старая, но что делает эта функция? В примере она вызывается, но нет ее инициализации.
Dimension
Dimension
547 / 428 / 132
Регистрация: 08.04.2014
Сообщений: 1,693
Завершенные тесты: 1
20.11.2015, 17:57     Алгоритм Дейкстры #7
выбирает минимум из двух чисел ,она встроена
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.11.2015, 18:09     Алгоритм Дейкстры
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
forze96
0 / 0 / 0
Регистрация: 12.11.2014
Сообщений: 11
20.11.2015, 18:09     Алгоритм Дейкстры #8
Работаю в С++builder - ругается. Предложите аналогию, пожалуйста. Спасибо

Добавлено через 5 минут
C
1
#define MIN(a, b) ((a) < (b) ? (a) : (b))
Решено.
Yandex
Объявления
20.11.2015, 18:09     Алгоритм Дейкстры
Ответ Создать тему
Опции темы

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