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

Жадный граф/алгоритм

20.04.2014, 21:19. Показов 2942. Ответов 1
Метки нет (Все метки)

Требуется написать программу с графическим интерфейсом:
пользователь задаёт точки (A, B, C и т.д.). Далее соединяет между собой какие-то точки (B-C, C-A и т.п.) и задаёт их соединениям вес (1, 4, 3 и т.п.). После пользователь указывает две точки из существующих (A и B, B и C и т.п.) и программа определяет самый длинный ("тяжёлый" по весу) путь из одной указанной точки в другую.
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
20.04.2014, 21:19
Ответы с готовыми решениями:

Жадный алгоритм
Задача: По следам олимпиады. Известно, что оптимальным выбором лыж является такой, когда длина лыж...

жадный алгоритм
написать программу для жадного алгоритма, если не сложно с комментариями в действиях

Жадный алгоритм
Суть задачи - имеется N предметов различного размера. Один ящик имеет строгую вместимость....

Жадный алгоритм С++
С целью борьбы с теневой экономикой банк решил внедрить объединение N счетов фирмы в один. За одну...

1
Мой лучший друг-отладчик!
166 / 166 / 30
Регистрация: 24.06.2012
Сообщений: 662
Записей в блоге: 5
20.04.2014, 22:38 2
Лучший ответ Сообщение было отмечено UraNick как решение

Решение

UraNick, обычная Дейкстра(если веса рёбер положительны), или Форд-Беллман(а там уже всё равно, какие веса).Только оптимизируйте не на наименьший вес, а на наибольший - там просто знак местами поменять. Вот вам алгоритм Дейкстры:
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
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
 
using namespace std;
 
const int maxe=100,maxv=100;
int ef[maxe],es[maxe],ev[maxe],next[maxe],first[maxv],c=0,i;
vector<long long> d(maxv+1,100000000),p(maxv+1);
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;
 
 
void add(int v1,int v2,int value)
{
    next[++c]=first[v1];first[v1]=c;
    ef[c]=v1;es[c]=v2;ev[c]=value;
}
 
void init()
{
    int x,y,z;
    for(i=0;i<5;++i)
    {
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
        add(y,x,z);
    }
}
 
void dist()
{
    int s=1;
    d[s]=0;
    q.push(make_pair(0,s));
    while(!q.empty())
    {
        int to=q.top().second;int line=q.top().first;
        q.pop();
        if(line>d[to])  continue;
        for(int h=first[to];h;h=next[h])
            if(line+ev[h] < d[es[h]])
            {
                d[es[h]]=line+ev[h];
                p[es[h]]=to;
                q.push(make_pair(d[es[h]],es[h]));
            }
    }
}
 
int main()
{
    init();
    dist();
    cout<<d[2]<<endl;
    system("pause");
    return 0;
}
вот Форд
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
//Надо помнить, что если рёбра двунаправлены, то бежать по 2*m.
//И если нужно найти цикл, то просто делаем ещё 1 проход, и фиксируем булевой переменной
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <vector>
 
using namespace std;
typedef long long ll;
 
const ll maxv=100,maxe=10000;
ll ef[maxe],es[maxe],ev[maxe],first[maxv],next[maxe],c=0;
ll n,m,i,j,k,x,y,z,s;
vector<ll> d(maxv,100000000);
void init(ll v1,ll v2,ll val)
{
    next[++c]=first[v1];first[v1]=c;
    ef[c]=v1;es[c]=v2;ev[c]=val;
}
 
void ford()
{
    d[s]=0;
    for(i=1;i<n;++i)
    {
        for(j=1;j<=m;++j)
        {
            if(d[ef[j]]+ev[j]<d[es[j]])
                d[es[j]]=d[ef[j]]+ev[j];
        }
    }
}
 
void sol()
{
    cin>>n>>m>>s;
    for(i=0;i<m;++i)
    {
        cin>>x>>y>>z;
        init(x,y,z);
    }
    ford();
}
 
int main()
{
    sol();
    cout<<d[2]<<endl;
    system("pause");
    return 0;
}
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
20.04.2014, 22:38
Помогаю со студенческими работами здесь

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

Жадный алгоритм
Добрый день. Помогите, пожалуйста, понять, где затаилась ошибка. Это задачка на жадный алгоритм:...

Жадный алгоритм (рюкзак)
слишком медленно, но верно работает программа. Помогите пожалуйста ускорить. (извиняюсь за транслит...

Жадный алгоритм на графе
Собственно, нужно написать программу поиска кратчайшего пути на графе &quot;жадным методом&quot;. То есть,...


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

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

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