0 / 0 / 0
Регистрация: 29.03.2019
Сообщений: 7
1

Как реализовать Алгоритм Беллмана-Форда со смежной матрицей?

29.03.2019, 21:59. Показов 2380. Ответов 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
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
#include "pch.h" 
#include <iostream>
#define inf 100000
using namespace std;
struct Edges {
    int u, v, w;
};
const int Vmax = 1000;
const int Emax = Vmax * (Vmax - 1) / 2;
int i, j, n, e, start;
Edges edge[Emax];
int d[Vmax];
//алгоритм Беллмана-Форда
void bellman_ford(int n, int s)
{
    int i, j;
 
    for (i = 0; i < n; i++) d[i] = inf;
    d[s] = 0;
 
    for (i = 0; i < n - 1; i++)
        for (j = 0; j < e; j++)
            if (d[edge[j].v] + edge[j].w < d[edge[j].u])
                d[edge[j].u] = d[edge[j].v] + edge[j].w;
 
    for (i = 0; i < n; i++) if (d[i] == inf)
        cout << endl << start << "->" << i + 1 << "=" << "Not";
    else cout << endl << start << "->" << i + 1 << "=" << d[i];
}
//главная функция
void main()
{
    setlocale(LC_ALL, "Rus");
    int w;
 
    cout << "Количество вершин > "; cin >> n;
    e = 0;
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++)
        {
            cout << "Вес " << i + 1 << "->" << j + 1 << " > "; cin >> w;
            if (w != 0)
            {
                edge[e].v = i;
                edge[e].u = j;
                edge[e].w = w;
                e++;
            }
        }
 
    cout << "Стартовая вершина > "; cin >> start;
    cout << "Список кратчайших путей:";
    bellman_ford(n, start - 1);
    system("pause>>void");
}
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
29.03.2019, 21:59
Ответы с готовыми решениями:

Алгоритм форда беллмана
Необходимо реализовать поиск кратчайшего пути в графе между заданными вершинами методом...

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

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

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

1
391 / 259 / 194
Регистрация: 02.05.2017
Сообщений: 1,003
30.03.2019, 10:16 2
Цитата Сообщение от asqw22 Посмотреть сообщение
смежными графами
каво?

------------------------------------
Если вместо списка ребер (с которым алгоритму работать легче) у вас дана матрица смежности, то надо либо заменить цикл в 22 строке на 2 новых, которые перебирают всю матрицу и смотрят все ребра, что не всегда хорошо, особенно если граф разреженный, либо

матрица смежности --> список ребер и запускать уже как запускаете сейчас
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
30.03.2019, 10:16
Помогаю со студенческими работами здесь

Алгоритм Беллмана-Форда
Здравствуйте всем. Я вообще редко обращаюсь сюда за помощью решить задачу и стыдно как то, но я не...

Реализовать алгоритм Форда-Беллмана
Дядьки И Тетьки помогите разобраться. Есть такое условие:Реализовать алгоритм Форда-Беллмана для...

Алгоритм Форда-Беллмана
У меня есть код алгоритма, но мне его надо переделать так, чтобы я сам вводил матрицу ( состоящую...

Алгоритм Форда-Беллмана.
Поиск кратчайшего пути, а также обход в глубь для поиска всех путей.


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2023, CyberForum.ru