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

как найти путь по алгоритму дейкстры - C++

Восстановить пароль Регистрация
 
Stas12
0 / 0 / 0
Регистрация: 20.10.2011
Сообщений: 102
18.12.2011, 12:42     как найти путь по алгоритму дейкстры #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
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
#include "stdafx.h"
#include<iostream>
#include<fstream>
#include<conio.h>
#include<locale.h>
#include<iomanip>
 
using namespace std;
 
int min(int *a); // прототип функции
int **Graf; // объявляем матрицу смежности
int *Label; // объявляем массив меток
int *Active; // объявляем массив
int *pred;
int i,j,k;
int Start, N, M, V, Last;
 
int main()
{
    setlocale(LC_ALL, "Russian");
    ifstream input("map.txt");
    input>>N>>M>>Start>>Last;
    Graf= new int * [N];
    for(i=0;i<N;i++) 
    {
        Graf[i]= new int [N];
    }
    for(i=0;i<N;i++) 
        for(j=0;j<N;j++) 
            Graf[i][j]=0;
    for(k=0;k<M;k++)
    {
        input>>i>>j>>V; 
        Graf[i][j]=V; 
        Graf[j][i]=V;
    }
    cout<<"Матрица смежности:"<<endl;
    for(i=0; i<N; i++)
    {
        for(j=0; j<N; j++)
            cout<<setw(3)<<Graf[i][j];
        cout<<"\n";
    }
    Label= new int [N];
    Active= new int [N];
    pred=new int[N];
    for(i=0;i<N;i++) 
    {
        Active[i]=0;
        pred[i]=0;
    }
    for(i=0;i<N;i++) 
        Label[i]=32767;
    Active[Start]=1; 
    Label[Start]=0;
    i=Start;
    cout<<"\nActive:\t";
    for(j=0; j<N; j++ )
        cout<<Active[j]<<" ";
    cout<<"\nLabel:\t";
    for(j=0; j<N; j++ )
        cout<<Label[j]<<" ";
    
    do
    { 
        for(j=0;j<N;j++)
            if(Graf[i][j]!=0 && Label[j]> Label[i]+ Graf[i][j])
            {
                cout<<"\n\n";
                Active[j]=1; // помечаем вершину
                Label[j]= Label[i]+ Graf[i][j]; 
                pred[j]=i;// вставка 4
                cout<<"\nActive:\t";
                for(int p=0; p<N; p++)
                {
                    cout<<Active[p]<<" ";
                }
                cout<<"\nLabel:\t";
                for(int p=0; p<N; p++ )
                    cout<<Label[p]<<" ";
            }
            Active[i]=0;
            i=min(Label);
    } while(i!=-1);
    // вывод результата
    cout<<"\n\n";
    cout<<"\nActive:\t";
    for(int p=0; p<N; p++)
    {
        cout<<Active[p]<<" ";
    }
    cout<<"\nLabel:\t";
    for(int p=0; p<N; p++ )
        cout<<Label[p]<<" ";
 
 
    cout<<"\nДлина маршрута до "<<Last<<" = "<<Label[Last]<<endl;
    int *Temp;
    Temp=new int [N];
    
    getch();
    return 0;
} 
 
int min(int *a)
{
    int min=32767,k, min_pos=-1;
    for(k=0; k<M;k++)
        if(a[k]< min && Active[k]==1)
        {
            min=a[k]; 
            min_pos=k;
        }
        return min_pos;
}
файл graf.txt


6 8 0 5
0 1 2
0 4 3
1 2 1
1 3 4
1 4 3
1 5 7
2 5 2
3 4 3



помогите, а то никак не получается((
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
18.12.2011, 12:42     как найти путь по алгоритму дейкстры
Посмотрите здесь:

помогите, неправильно выводит путь алгоритм Дейкстры C++
Найти путь к файлу C++
Задача на алгоритм Дейкстры (как лучше хранить информацию?) C++
C++ Вычисление НОД по алгоритму Евклида (как организовать код?)
Найти путь с минимальными затратами энергии C++
C++ Найти кратчайший путь из вершины u в вершину v
Как найти кратчайший путь в лабиринте? C++
C++ Как найти НЕ Кратчайший путь в графе ?

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

Текущее время: 00:09. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru