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

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

Восстановить пароль Регистрация
Другие темы раздела
C++ Размер стэка и кучи http://www.cyberforum.ru/cpp-beginners/thread1030065.html
Насколько я знаю, куча и стек растут в направлении друг-дружки в общей куче. Однако, я с удивление обнаружил, что выделить локальный массив на > миллиона элементов типа int нельзя, а в куче (new) можно. Выходит, стэк ограничен? Но почему? Его можно сделать динамических поигравшись с опциями компилятора? Или, быть может, динамический стек => динамическая куча (в смысле, когда границы её меняются...
C++ Дано натуральное число, верно ли что её первая цифра превышает m (вводится с клавиатуры ) Дано натуральное число, верно ли что её первая цифра превышает m (вводится с клавиатуры ) http://www.cyberforum.ru/cpp-beginners/thread1030049.html
C++ Функция
Друзья, возникла проблемка, прошу помощи( На скрине описание) int _in() { int rand,i; srand((unsigned)time(NULL)); //генератор случайных чисе int n =40; // константа n целого типа int *mass1 = new int; //выделяем память под массив в количестве n элементов for (i=0; i<n; i++) //цикл по элементам массива std::cout<<mass1=rand()%50+1<<std::setw(4); //примваиваем значение текущему ...
Разложите пожалуйста по шагам выражение a^=b++==3?--c:b---c C++
Разложите пожалуйста по шагам выражение a^=b++==3?--c:b---c, в какой последовательности считать (приоритеты)
C++ Решение СЛАУ методом переменных направлений http://www.cyberforum.ru/cpp-beginners/thread1030014.html
Помогите, пожалуйста. Нужно реализовать программу решения системы линейных уравнений методом переменных направлений.
C++ Интерактивные циклы Помогите сделать, кто чем сможет! Составить программу вычисления значений функции в точках хi принадлежит , хi = х0 + i дельта х, i = 0,1, …, воспользовавшись формулами разложения элементарных функций в ряд Тейлора с точностью эпсилон = 10 –6 степени. Вывести на экран необходимое количество слагаемых в каждом случае. Сравнить результаты со значениями функции в этих точках, вычисленных с... подробнее

Показать сообщение отдельно
ZaMaZaN4iK
Мой лучший друг-отладчик!
 Аватар для ZaMaZaN4iK
163 / 163 / 9
Регистрация: 24.06.2012
Сообщений: 662
Записей в блоге: 5
Завершенные тесты: 1
05.12.2013, 20:28     Найдите кратчайший путь в графе
что-то я не совсем понял, что вы хотите, но попытаюсь.Вот код инициализации графа списком ребер и нахождения кратчайшего пути в графе от одной вершины до другой алгоритмом Дейкстры:
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;
}
 
Текущее время: 18:57. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru