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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 33, средняя оценка - 4.91
shPavel25
6 / 6 / 0
Регистрация: 29.03.2011
Сообщений: 44
#1

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

30.07.2012, 20:52. Просмотров 5022. Ответов 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)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
30.07.2012, 20:52
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Алгоритм Дейкстры (C++):

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

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

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

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

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

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

7
nameless
Эксперт С++
334 / 298 / 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/b1497ccbb69fca0c124b6aa58cf6ba93

Со считыванием проблем возникнуть не должно..
3
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;
}
1
shPavel25
6 / 6 / 0
Регистрация: 29.03.2011
Сообщений: 44
31.07.2012, 00:57  [ТС] #4
Спасибо
0
bubliq
0 / 0 / 0
Регистрация: 10.03.2013
Сообщений: 18
09.07.2015, 17:09 #5
ваш код не работает
0
forze96
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
Dimension
571 / 440 / 135
Регистрация: 08.04.2014
Сообщений: 1,709
Завершенные тесты: 1
20.11.2015, 17:57 #7
выбирает минимум из двух чисел ,она встроена
0
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))
Решено.
0
20.11.2015, 18:09
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.11.2015, 18:09
Привет! Вот еще темы с ответами:

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

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

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

Рекурсивный алгоритм Дейкстры - C++
Добрый день, необходима помощь в алгоритме trains - матрица, сохраняющая длины ребер stations - количество графов start - граф, с...


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

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

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