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

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

Войти
Регистрация
Восстановить пароль
 
Космонавт_
0 / 0 / 0
Регистрация: 24.04.2011
Сообщений: 30
#1

Дейкстра на куче - C++

15.06.2011, 09:57. Просмотров 584. Ответов 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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
#include <stdio.h>
#include <malloc.h>
const int m=50;
const int n=5;
const int B=10000;
 
struct heap
{
    int versh[m];
    int d[m];
};
 
FILE*fi=fopen("fin_d.txt", "r");
FILE*fo=fopen("fout_d.txt", "w");
 
heap q;
int head=1;
int tail=1;
int was[n+1];
int a[n+1][n+1];
 
int empty ()
{
    if (tail==head) return 1;
    else return 0;
}
 
void push (int a, int lway)
{
    int t, vrem, p=1;
    if (!empty())
    {
        q.d[tail]=lway;
        t=tail;
        tail++;
        while ((p!=0)&&(t!=1))
        {
            if (q.d[t]<q.d[t/2])
            {
                vrem=q.d[t];
                q.d[t]=q.d[t/2];
                q.d[t/2]=vrem;
                t/=2;
            }
            else p=0;
        }
        q.versh[t]=a;
    }
    else 
    {
        q.d[tail]=lway;
        q.versh[tail]=a;
        tail++;
    }
}
 
int pop (int a)
{ 
    int t, s=0, vrem, p=1, temp, exit=-1;
    int i;
    if (!empty())
    {
        temp=q.versh[1];
        i=1;
        while (i<=tail-1)
            if (temp==a)
            {
                exit=q.d[i];
                q.d[i]=q.d[tail-1];
                q.versh[i]=q.versh[tail-1];
                tail--;
                t=i;
                while ((p!=0)&&(t<tail)&&(2*t<tail))
                {
                    if (q.d[t*2+1]<q.d[t*2])
                        s=t*2+1;
                    if (q.d[t*2+1]>=q.d[t*2]) 
                        s=t*2;
                    if (q.d[s]<q.d[t])
                    {
                        vrem=q.d[t];
                        q.d[t]=q.d[s];
                        q.d[s]=vrem;
                        vrem=q.versh[t];
                        q.versh[t]=q.versh[s];
                        q.versh[s]=vrem;
                        t=s;
                    }
                    else 
                        p=0;
                }
                i=10;
            }
            else 
            {
                i++;
                temp=q.versh[i];
            }
    }
    return exit;
}
 
void deikstra (int v)
{
    int i, j, length, lnv, w;
    for (i=1; i<=n; i++)
        if (i!=v)
            push (i, B);
        else
            push (i, 0);
 
    while (!empty())
    {
        lnv=pop(v);
        was [v]=1;
        for (w=1; w<=n; w++)
            if ((was[w]==0)&&(a[v][w]!=-1)) 
            {
                length=pop (w);
                if (length>lnv+a[v][w] && length!=-1)
                {
                    length=lnv+a[v][w];
                    push (w, length);
                }
                lnv=length;
            }
    }
}
 
void print ()
{  
    int i;
    if (!empty())
    {
        for (i=head; i<tail; i++)
            printf("%d ", q.d[i]);
        printf ("\n");
    }
    else
        printf ("Heap is empty.\n");
}
 
void main()
{   
    int i, j, beg, end;
    for (i=0; i<n; i++)
        was[i]=0;
    fscanf (fi, "%d", &beg);
    fscanf (fi, "%d", &end);
    for (i=1; i<=n; i++)
        for (j=1; j<=n; j++)
            fscanf (fi, "%d", &a[i][j]);
    deikstra (beg);
    fprintf (fo, "way:   %d", q.d[end]);
    fclose (fi);
    fclose (fo);
}
Добавлено через 2 минуты
Помогите с исправлением багов, пожалуйста
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
15.06.2011, 09:57
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Дейкстра на куче (C++):

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

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

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

Матрица Форда Беллмана и метод Дейкстра - C++
Тут такая проблема , задали написать матрицу с помощью єтих методов/ вопрос : Как вставить сюда матрицу (тоесть с помощью методов Беллмана...

Удаление кучи в куче - C++
Доброго. У меня возник такой вопрос: имею я некую структуру struct inbase { int *data; }; в коде (не важно где) я...

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

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
15.06.2011, 09:57
Привет! Вот еще темы с ответами:

Потоки и выделение памяти в куче - C++
Подскажите, кто знает, какие есть тонкости при выделении памяти в куче (new) в потоках отличных от главного. У меня возникают исключения...

Расположение данных в стеке и в куче - C++
Друзья, возник вопрос. Следующий код char length_buffer; ...заполнение length_buffer двоичным представлением целого числа 999... ...

Указатели (Выделение памяти в куче) - C++
Чтобы создать в динамически распределяемой памяти переменную типа unsigned short необходимо написать следующее: unsigned short...

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


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

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

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