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

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

26.03.2018, 16:34. Показов 486. Ответов 2
Метки нет (Все метки)

Мне нужно написать функцию алгоритма Дейстра. В интернете есть много примеров. и в книге Фундаментальные алгоритмы С ++ Сэндвик, но у меня не получается под свой код сделать ((Нужна ваша помощь. Я написала что знаю. Но и этот код не гарантирую что правильный. У меня есть как параметр граф и начало и конец вектора VertexList. Буду благодарна за помощь в реализации моего кода
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
std::vector<unsigned> Graph::Dijkstra(const Graph & graph, int startVertex, int endVertex)
{
    std::vector<unsigned> shortestPath(10);
    for (unsigned vertex = 0; vertex < mVertexList.size(); ++vertex)
        shortestPath.emplace_back(vertex);
 
    while (!shortestPath.empty()) 
    {
        AdjacencyList adjacencyList  = getAdjacencyList(endVertex - startVertex);
        for (Edge* edge = adjacencyList.cbegin(); !adjacencyList.cend();)
        {
            int weight = edge->mWeight;
        }
    }
    return shortestPath;
}
Функции мои:
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
Edge::Edge(unsigned start, unsigned end, float weight)
    : mStart(start)
    , mEnd(end)
    , mWeight(weight)
{
}
 
 
Node::Node(unsigned end, float weight)
    : mEnd(end)
    , mWeight(weight)
{}
 
Graph::Graph(unsigned maxVertexCount)
    : mVertexList(maxVertexCount)
{
}
 
 
const Graph::AdjacencyList& Graph::getAdjacencyList(unsigned vertex) const 
{
    assert(vertex < mVertexList.size());
    return mVertexList[vertex];
}
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
26.03.2018, 16:34
Ответы с готовыми решениями:

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

Алгоритм Дейкстра
Есть у кого исходник кода,чтобы проверяло достижимость из выбранного города во все остальные? или...

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

Матрица Форда Беллмана и метод Дейкстра
Тут такая проблема , задали написать матрицу с помощью єтих методов/ вопрос : Как вставить сюда...

__________________

Записывайтесь на профессиональные курсы C++ разработчиков
2
3 / 3 / 4
Регистрация: 18.06.2015
Сообщений: 19
26.03.2018, 17:43 2
Может, пригодится вам, осталось с универа:

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
#include <stdio.h>
#include <string.h>
#include "stdlib.h"
#include "conio.h"
#include "math.h"
#include <iostream>
using namespace std;
const int inf = 999; 
 
const int vertex = 7;  
 
int M[vertex][vertex] = 
{ 
{0 ,1,inf,3,inf,inf,2},
{1,0,4,3,inf,6,inf},
{inf,4,0,1,inf,2,2},
{3,3,1,0,2,inf,inf},
{inf,inf,inf,2,0,2,4},
{inf,6,2,inf,2,0,inf },
{2,inf,2,inf,4,inf,0 } 
};
 
int W[vertex] = {0};
int Dw[vertex] = {0};
 
void print(int M[][vertex], int R[][vertex], int S[vertex]) // вывод
{
    int step = 0;
    printf("\nM:");
    
    for (int i = 0; i < vertex; i++)
    {
        printf("\n");
         for (int j = 0; j < vertex; j++)
            {
                if (M[i][j] == inf)
                    printf("\t -");
                        else
                         printf("\t%d", M[i][j]);
        }
        printf("\n");
    }
 
    printf("R:\n\n");
    printf("\tS");
    printf("\t\t\t\tw");
    printf("\tD(w)");
    
    for (int i = 0;i < vertex; i++)
    printf("\tD(%d)",i);
    
    for (int i = 0; i < vertex; i++)
    {
        printf("\n");
        printf("(");
        
      for (int i = 0; i <= step; i++)
      { 
        if(S[i] ||  i==0)
            if(i != step)
                printf("%d,", S[i]);
            else 
                printf("%d", S[i]);
      }
 
        printf(")\t");
        printf("\t\t");
    
      if (step <= vertex / 2)
        printf("\t");
        
      if(W[i])
        printf("\t%2d",W[i]);
      else 
        printf("\t -");
        
      if(Dw[i]) 
        printf("\t%2d",Dw[i]);
      else 
        printf("\t -");
            
      for (int j = 0; j < vertex ; j++)
      {
            if (R[i][j] == 0 || R[i][j] == inf) 
                printf("\t -");
            else
                printf("\t%2d", R[i][j]);
      }
        printf("\n");
        step++;
    }
    
    
}
 
int getMinimal(int A, int B) // возвращает минимум
{
    if (A <= B) 
        return A;
    else 
        return B;
}
 
bool entryVertex(int *Array, int toFind) // смотрит, взяли ли мы уже эту вершину
{
    for (int i = 0; i < vertex; i++)
    {
        if (toFind == Array[i])
            return true;
    }
    return false;
}
 
int getMinimalLine(int R[][vertex], int *D, int k) // ищет минимальное значение в строке
{
    int minimal = inf;
    int minimalIndex;
 
    for (int i = 0; i < vertex; i++)
    {
        if (entryVertex(D, i) == false)
          if (R[k][i] <= minimal)
          {
            minimal = R[k][i];
            minimalIndex = i;
          }
    }
    return minimalIndex;
}
 
int main()
{
    
    int R[vertex][vertex];
    int D[vertex];
 
    int s = 0, w = 0, k = 0, d = 0, minimalIndex;
 
    for (int i = 0; i < vertex; i++) // заполняем все нолями
        for (int j = 0; j < vertex; j++)
            R[i][j] = 0;
 
    for (int i = 0; i < vertex+1; i++) // это путь, по-моему
        D[i] = 0;
 
    for (int j = 0; j < vertex; j++)
        R[k][j] = M[k][j]; 
    
 
    minimalIndex = getMinimalLine(R, D, k); // ищем минимальное значение в строке, получаем индекс
 
    s = R[k][minimalIndex]; // выбираем элемент
    w = minimalIndex; //  запоминаем его иднекс
    D[d] = minimalIndex; // вносим его в наш путь
    d++; // переходим на следующий шаг
    
    for(k=1;k<vertex;k++) // для всех следующих шагов
    {
        W[k] = w; // добавляемая вершина
        Dw[k] = s; //
        
        for (int j = 1; j < vertex; j++)
        {
            if (entryVertex(D, j) == false) // если еще не брали вершину
            {
                R[k][j] = getMinimal(R[k - 1][j], Dw[k] + M[W[k]][j]); // добавляем ее, считаем общую стоимость пути (по-моему, хз)
                minimalIndex = getMinimalLine(R, D, k); // ищем минимальный в строчке
            }
        }
        s = R[k][minimalIndex]; // выбираем элемент
        w = minimalIndex; // запоминаем его индекс
        D[d] = minimalIndex; // добавляем в путь
        d++; // следующий шаг
    }
    print(M, R, D);
    
    return 0;
}
0
353 / 134 / 28
Регистрация: 16.12.2012
Сообщений: 607
Записей в блоге: 1
26.03.2018, 20:22 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
std::vector<unsigned> Graph::Dijkstra(const Graph & graph, int startVertex, int endVertex)
{
    std::vector<unsigned> shortestPath(graph.mVertexList.size(), inf); // где inf - большая константа 
        shortestPath[startVertex] = 0;
        set<pair<int, int> > s;
        s.insert(make_pair(0, startVertex));
    while (!s.empty()) 
    {
                int vertex = s.begin()->second;
                int w = s.begin()->first;
                s.erase(s.begin());
                if (shortestPath[vertex] < w) continue;
        AdjacencyList adjacencyList  = getAdjacencyList(vertex);
        for (Edge* edge = adjacencyList.cbegin(); !adjacencyList.cend();)
        {
            int weight = edge->mWeight;
                        if (shortestPath[edge->mEnd] > w+weight) 
                        {
                               shortestPath[edge->mEnd] = w+weight;
                               s.insert(make_pair(shortestPath[edge->mEnd], mEnd));
                        }
         
        }
    }
    return shortestPath;
}
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
26.03.2018, 20:22

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

Нужен алгоритм поиска пути в этом лабиринте (будь то волновой алгоритм или алгоритм правой/левой руки )
#include &quot;stdafx.h&quot; #include &lt;iostream&gt; #include &lt;conio.h&gt; using namespace std; void lab...

Волновой алгоритм поиска (Алгоритм A* / Алгоритм А стар)
Хочу разработать алгоритм для решения головоломки с подвижными дисками (перестановочная...

Алгоритм дейкстра
Нужно запрограммировать алгоритм Дейкстра. Не понимаю как можно дальше найти путь в массиве для...

Алгоритм Дейкстра
Здравствуйте! Помогите пожалуйста!! У меня в программе есть такое: //Вывод результата ...


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

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

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