Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.72/36: Рейтинг темы: голосов - 36, средняя оценка - 4.72
6 / 6 / 0
Регистрация: 29.03.2011
Сообщений: 47
1

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

30.07.2012, 20:52. Просмотров 7144. Ответов 7
Метки нет (Все метки)

Добрый день, помогите пож-та решить задачи на с++. Нашел решение (расписаны все алгоритмы, процедуры подсчета и т. д.), но сложность состоит в том, что я не понимаю строищихся структур и вообще никогда не программировал на 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;
}
}
}
}
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
30.07.2012, 20:52
Ответы с готовыми решениями:

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

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

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

Алгоритм Дейкстры
Всем доброго дня! Столкнулся с проблемой, никак не могу понять, как лучше реализовать алгоритм...

7
Эксперт С++
340 / 304 / 36
Регистрация: 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/... a58cf6ba93

Со считыванием проблем возникнуть не должно..
3
14 / 14 / 3
Регистрация: 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;
}
1
6 / 6 / 0
Регистрация: 29.03.2011
Сообщений: 47
31.07.2012, 00:57  [ТС] 4
Спасибо
0
0 / 0 / 0
Регистрация: 10.03.2013
Сообщений: 18
09.07.2015, 17:09 5
ваш код не работает
0
0 / 0 / 0
Регистрация: 12.11.2014
Сообщений: 11
20.11.2015, 17:54 6
C
1
min(d[v] + g[v][j], d[j]);
Понимаю, что тема старая, но что делает эта функция? В примере она вызывается, но нет ее инициализации.
0
Dimension
579 / 447 / 223
Регистрация: 08.04.2014
Сообщений: 1,710
20.11.2015, 17:57 7
выбирает минимум из двух чисел ,она встроена
0
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))
Решено.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
20.11.2015, 18:09

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Алгоритм Дейкстры
Добрый день! Можете пожалуйста помочь с задачкой. Очень прошу так как сам не разобрался как...

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

Алгоритм Дейкстры
Что-то у меня Дейкстра не работает... прошу помощи у вас... Сам уже часа 1.5 сижу и не могу найти...

Алгоритм Дейкстры
Ребятушки, помогите, пожалуйста. Нужна реализация алгоритма дейкстры на паскале, а именно вот этого...


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

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

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