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

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

Войти
Регистрация
Восстановить пароль
 
baykonurr
11 / 11 / 1
Регистрация: 19.02.2013
Сообщений: 101
#1

Найдите кратчайший путь в графе - C++

05.12.2013, 20:18. Просмотров 486. Ответов 2
Метки нет (Все метки)

Создайте граф согласно своего варианта в среде С + +, длины путей задайте самостоятельно, найдите кратчайший путь в графе, используя указанный метод.
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.12.2013, 20:18
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Найдите кратчайший путь в графе (C++):

Кратчайший путь в графе. - C++
Такая задача: Дан ориентированный взвешенный ациклический граф. Требуется найти в нем кратчайший путь из вершины s в вершину t. ...

Кратчайший путь в графе(Рекурсия) - C++
Я реализовал программу с помощью алгоритма флойда.Препод придрался к тому что я реализовал без рекурсии. Помогите изменить прогу под...

Как найти НЕ Кратчайший путь в графе ? - C++
Мне нужно найти не кратчайший путь в графе от одной вершины к другой, граф неориентированный, задан списком смежности типа: 5 1 1 2 3...

Графы кратчайший путь ! - C++
Помогите написать функцию для поиска кратчайшего пути между вершинами которые задаются с клавы я написал правда получилось что это...

Кратчайший путь коня с++ - C++
помогите пожалуйста написать алгоритм кротчайшего пути коня на шахматной доске из А в Б

Найти кратчайший путь шахматного короля - C++
Здравствуйте, имеется задача: Есть шахматное поле NxM N, M ≤ 10^9 На шахматном поле отмечено два прямоугольника размерами не менее...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Tsin
05.12.2013, 20:23
  #2

Не по теме:

baykonurr, создал. Теперь ваша очередь.

0
ZaMaZaN4iK
Мой лучший друг-отладчик!
164 / 164 / 9
Регистрация: 24.06.2012
Сообщений: 662
Записей в блоге: 5
Завершенные тесты: 1
05.12.2013, 20:28 #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
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;
}
1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.12.2013, 20:28
Привет! Вот еще темы с ответами:

Найти самый кратчайший путь в массиве - C++
У меня есть динамический массив в котором количество строк задаётся при выполнении программы, а количество строк неизменно и равно 3. Мне...

Найти кратчайший путь из вершины u в вершину v - C++
Уффф, к завтрашнему дню нужно сдать эти задачи, помогите пожалуйста кто чем сможет :sorry: (следующие задачи через обходы в глубину и...

Как найти кратчайший путь в лабиринте? - C++
Чтобы найти кратчайший путь в лабиринте использую волновой алгоритм, его сделал, но вот кратчайший путь не получается восстановить. ...

Графы, расположить людей по билетам, кратчайший путь - C++
Здравствуйте. На соревнованиях codeforces я часто замечаю, что больше половины задач на тему графов, где нужно находить кратчайший путь или...


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

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

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