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

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

Войти
Регистрация
Восстановить пароль
 
vitalicok
0 / 0 / 0
Регистрация: 05.02.2014
Сообщений: 2
#1

Матрица Форда Беллмана и метод Дейкстра - C++

05.02.2014, 15:48. Просмотров 810. Ответов 2
Метки нет (Все метки)

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

std::vector<int> FORD_BELLMAN(int n, std::vector<std::vector<int> > &A, int s)
{
std::vector<int> D(n+1);
for (int v=1; v<=n; ++v)
D[v] = A[s][v];
D[s]=0;
for (int k=1; k<=n-2; ++k)
for (int v=1; v<=n; ++v)
if (v!=s)
for (int u=1; u<=n; ++u)
D[v]=std::min(D[v], D[u] + A[u][v]);
return D;
}



std::vector<int> DIJKSTRA(int n, std::vector<std::vector<int> > &A, int s)
{
std::vector<int> D(n+1);
for (int v=1; v<=n; ++v)
D[v] = A[s][v];
D[s]=0;
std::list<int> T;
/* T = V/{s} */
for (int v=1; v<=n; ++v)
if (v!=s)
T.push_back(v);

while (!T.empty()){
/* u = dowolny wierzcholek r taki, ze D[r]=min{D[p]: p nalezy do T} */
/* it - iterator na u */
std::list<int>::iterator it = T.begin();
for(std::list<int>::iterator i = T.begin(); i!=T.end(); ++i)
/* UWAGA na blad w ksiazce -> if(*i < *it) it = i; */
if (D[*i] < D[*it]) it = i;
int u = *it;
T.erase(it); /* T=T/{u} */

for (std::list<int>::iterator i=T.begin(); i!=T.end(); ++i){
int v=*i;
D[v]=std::min(D[v], D[u] + A[u][v]);
}

}
return D;
}
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.02.2014, 15:48
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Матрица Форда Беллмана и метод Дейкстра (C++):

Алгоритм Форда-Беллмана - C++
Доброго времени суток. Есть кривой код: #include &lt;iostream&gt; #include &lt;vector&gt; using namespace std; const int inf = 1555; struct...

Алгоритм Форда - Беллмана - C++
Помогите пожалуйста понять что не так у меня. ограничение времени на тест: 1 сек. ограничение памяти на тест: 32768 KB. ввод:...

Алгоритм Форда-Беллмана - C++
Народ если есть у кого нибудь исходник выложите пожалуйста очень надо. А то везде одно и то же... И ничего не понятно толком=)

Восстановление пути из алгоритма Форда-Беллмана - C++
Реализовал алгоритм Форда-Беллмана, но не получается правильно восстановить пути, подскажите, где ошибаюсь. #define...

Входные данные. Метод Форда-Фалкерсона - C++
Доброго времени суток! Есть код, который работает и справляется с основной задачей - нахождением максимального потока сети методом...

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

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
НеСказочник
58 / 46 / 7
Регистрация: 12.11.2012
Сообщений: 347
Записей в блоге: 2
05.02.2014, 16:40 #2
Если реч об этом и вот этом, то Вам, скорее всего, нужно сначала откуда-то граф взять. Если нет, то уточните вопрос.



PS: хорошо бы для кода использовать теги [CODE] или [CPP], что бы было проще читать Ваши сообщения.
0
vitalicok
0 / 0 / 0
Регистрация: 05.02.2014
Сообщений: 2
06.02.2014, 21:59  [ТС] #3
Возможно граф и есть , но сейчас у меня его , а без него можно как то?
Как я уже написал, нужно написать код матрицы на основе этог0 метода(какбы простая матрица но с элементами этого метода(матрица любая может быть , например 2х3)


вот код:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
std::vector<int> FORD_BELLMAN(int n, std::vector<std::vector<int> > &A, int s)
{
std::vector<int> D(n+1);
for (int v=1; v<=n; ++v)
D[v] = A[s][v];
D[s]=0;
for (int k=1; k<=n-2; ++k)
for (int v=1; v<=n; ++v)
if (v!=s)
for (int u=1; u<=n; ++u)
D[v]=std::min(D[v], D[u] + A[u][v]);
return D;
}
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<int> DIJKSTRA(int n, std::vector<std::vector<int> > &A, int s)
{
std::vector<int> D(n+1);
for (int v=1; v<=n; ++v)
D[v] = A[s][v];
D[s]=0;
std::list<int> T;
for (int v=1; v<=n; ++v)
if (v!=s)
T.push_back(v);
 
while (!T.empty()){
std::list<int>::iterator it = T.begin();
for(std::list<int>::iterator i = T.begin(); i!=T.end(); ++i)
if (D[*i] < D[*it]) it = i;
int u = *it;
T.erase(it);
 
for (std::list<int>::iterator i=T.begin(); i!=T.end(); ++i){
int v=*i;
D[v]=std::min(D[v], D[u] + A[u][v]);
}
 
}
return D;
}
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.02.2014, 21:59
Привет! Вот еще темы с ответами:

АЛГОРИТМ ДЕЙКСТРА - C++
Доброго времени суток всем! У меня вопрос. Написала программку для нахождения кратчайшего пути (алгоритм Дейкстра), но мне надо её как то...

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

Матрица, метод пузырька - C++
Доброе время суток всем. Задали сделать данную задачку. Дана матрица, j-столбцы, i-элементы. Вывести первоначальную, затем вторую для...

Обратная матрица. Метод Гаусса—Жордана - C++
Здравствуйте. Пишу программку вычисления матриц и вот эта функция ( см. код ) компилируется и работает без ошибок, но считает не...


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

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

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