Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 75, средняя оценка - 4.79
zmei89
32 / 7 / 1
Регистрация: 10.09.2010
Сообщений: 835
#1

Алгоритм Дейкстры С++ - C++

12.01.2012, 15:38. Просмотров 10081. Ответов 8
Метки нет (Все метки)

Реализовать алгоритм поиска кратчайшего пути. Алгоритм Дейкстры. Представление графа – матрица смежности.


как можно после того как прога подсчитает результат, рисовался бы граф и этот самый короткий путь, который посчитала программа? чтоб Входные данные для программы (графы) читались из файла. и оценку сложности
Но код выдает ошибку

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
#include<iostream.h>
#include<string.h>
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#define word unsigned int
 
int i, j, n, p, xn, xk;
int flag[11];
word c[11][11], l[11];
char s[80], path[80][11];
 
int min(int n)
{
        int i, result;
        for(i=0;i<n;i++)
                if(!(flag[i])) result=i;
        for(i=0;i<n;i++)
                if((l[result]>l[i])&&(!flag[i])) result=i;
        return result;
}
 
word minim(word x, word y)
{
        if(x<y) return x;
        return y;
}
 
void main()
{
        cout<<"напишите число точек: ";
        cin>>n; 
        for(i=0;i<n;i++)
                for(j=0;j<n;j++) c[i][j]=0;
        for(i=0;i<n;i++)
                for(j=i+1;j<n;j++)
                {
                    cout<<" задайте длины рёбер  x"<<i+1<<" do x"<<j+1<<": ";
                    cin>>c[i][j];
                }
        cout<<"   ";
        for(i=0;i<n;i++) cout<<"    X"<<i+1;
        cout<<endl<<endl;
        for(i=0;i<n;i++)
        {
                printf("X%d",i+1);
                for(j=0;j<n;j++)
                {
                        printf("%6d",c[i][j]);
                        c[j][i]=c[i][j];
                }
                printf("\n\n");
        }
        for(i=0;i<n;i++)
                for(j=0;j<n;j++)
                        if(c[i][j]==0) c[i][j]=65535; //nekonecno
        cout<<" задайте начальную точку: ";
        cin>>xn;
        cout<<" задайте конечную точку: ";
        cin>>xk;
        xk--;
        xn--;
        if(xn==xk)
        {
                cout<<"Начальная и конечные точки совпадают."<<endl;
                getch();
                return;
        }
 
        for(i=0;i<n;i++)
        {
                flag[i]=0;
                l[i]=65535;
        }
        l[xn]=0;
        flag[xn]=1;
        p=xn;
        itoa(xn+1,s,10);
                for(i=1;i<=n;i++)
                {
                        strcpy(path[i],"X");
                        strcat(path[i],s);
                }
                do
                {
                        for(i=0;i<n;i++)
                                if((c[p][i]!=65535)&&(!flag[i])&&(i!=p))
                                {
                                        if(l[i]>l[p]+c[p][i])
                                        {
                                                itoa(i+1,s,10);
                                                strcpy(path[i+1],path[p+1]);
                                                strcat(path[i+1],"-X");
                                                strcat(path[i+1],s);
                                        }
                                        l[i]=minim(l[i],l[p]+c[p][i]);
                                }
                        p=min(n);
                        flag[p]=1;
                }
                while(p!=xk);
        if(l[p]!=65535)
        {
                cout<<"Put: "<<path[p+1]<<endl;
                cout<<"Dlina puti: "<<l[p]<<endl;
        }
        else
                cout<<"Путь не существует!"<<endl;
        getch();
}
 Комментарий модератора 
Используйте теги форматирования кода!
0
Миниатюры
Алгоритм Дейкстры С++  
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.01.2012, 15:38
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Алгоритм Дейкстры С++ (C++):

Алгоритм Дейкстры
Добрый день, помогите пож-та решить задачи на с++. Нашел решение (расписаны все...

Алгоритм Дейкстры
Всем добрый день,уважаемые программисты! Помогите пожалуйста решить вот эту...

Алгоритм Дейкстры
Что-то у меня Дейкстра не работает... прошу помощи у вас... Сам уже часа 1.5...

Алгоритм Дейкстры
Пытаюсь сейчас его понять, как я понял сперва надо оставить матрицу смежности,...

Алгоритм Дейкстры
Дан ориентированный взвешенный граф. Найдите кратчайшее расстояние от одной...

Алгоритм Дейкстры
Написал программу, проверил код, в MVS6 С++ компилируется без ошибок. Но вот не...

8
Арсенал
144 / 66 / 14
Регистрация: 30.12.2011
Сообщений: 137
12.01.2012, 15:54 #2
Подправил пример, работает на MSVS 2008

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<iostream>
#include<string.h>
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#include<clocale>
#define word unsigned int
 
using namespace std;
 
int i, j, n, p, xn, xk;
int flag[11];
word c[11][11], l[11];
char s[80], path[80][11];
 
int min(int n)
{
        int i, result;
        for(i=0;i<n;i++)
                if(!(flag[i])) result=i;
        for(i=0;i<n;i++)
                if((l[result]>l[i])&&(!flag[i])) result=i;
        return result;
}
 
word minim(word x, word y)
{
        if(x<y) return x;
        return y;
}
 
int main()
{
        setlocale(LC_ALL, "Russian_Russia.1251");
        cout<<"напишите число точек: ";
        cin>>n;
        for(i=0;i<n;i++)
                for(j=0;j<n;j++) c[i][j]=0;
        for(i=0;i<n;i++)
                for(j=i+1;j<n;j++)
                {
                    cout<<" задайте длины рёбер  x"<<i+1<<" do x"<<j+1<<": ";
                    cin>>c[i][j];
                }
        cout<<"   ";
        for(i=0;i<n;i++) cout<<"    X"<<i+1;
        cout<<endl<<endl;
        for(i=0;i<n;i++)
        {
                printf("X%d",i+1);
                for(j=0;j<n;j++)
                {
                        printf("%6d",c[i][j]);
                        c[j][i]=c[i][j];
                }
                printf("\n\n");
        }
        for(i=0;i<n;i++)
                for(j=0;j<n;j++)
                        if(c[i][j]==0) c[i][j]=65535; //nekonecno
        cout<<" задайте начальную точку: ";
        cin>>xn;
        cout<<" задайте конечную точку: ";
        cin>>xk;
        xk--;
        xn--;
        if(xn==xk)
        {
                cout<<"Начальная и конечные точки совпадают."<<endl;
                getch();
                return 0;
        }
 
        for(i=0;i<n;i++)
        {
                flag[i]=0;
                l[i]=65535;
        }
        l[xn]=0;
        flag[xn]=1;
        p=xn;
        itoa(xn+1,s,10);
                for(i=1;i<=n;i++)
                {
                        strcpy(path[i],"X");
                        strcat(path[i],s);
                }
                do
                {
                        for(i=0;i<n;i++)
                                if((c[p][i]!=65535)&&(!flag[i])&&(i!=p))
                                {
                                        if(l[i]>l[p]+c[p][i])
                                        {
                                                itoa(i+1,s,10);
                                                strcpy(path[i+1],path[p+1]);
                                                strcat(path[i+1],"-X");
                                                strcat(path[i+1],s);
                                        }
                                        l[i]=minim(l[i],l[p]+c[p][i]);
                                }
                        p=min(n);
                        flag[p]=1;
                }
                while(p!=xk);
        if(l[p]!=65535)
        {
                cout<<"Put: "<<path[p+1]<<endl;
                cout<<"Dlina puti: "<<l[p]<<endl;
        }
        else
                cout<<"Путь не существует!"<<endl;
        getch();
        return 0;
}
Добавлено через 1 минуту
Ругался на Cannot open include file: 'iostream.h': No such file or directory

вместо void main() -> int main() /*код*/ return 0;
0
zmei89
32 / 7 / 1
Регистрация: 10.09.2010
Сообщений: 835
12.01.2012, 16:11  [ТС] #3
входе выполнения компиляции на последнем шаге прозошла ошибка такая
0
Миниатюры
Алгоритм Дейкстры С++  
Арсенал
144 / 66 / 14
Регистрация: 30.12.2011
Сообщений: 137
12.01.2012, 16:21 #4
Дык, задал 3 точки, 4-той точки в природе не существует. Проверку от превышения числа точек поставь
0
zmei89
32 / 7 / 1
Регистрация: 10.09.2010
Сообщений: 835
12.01.2012, 16:27  [ТС] #5
все заработало

как можно после того как прога подсчитает результат, рисовался бы граф и этот самый короткий путь, который посчитала программа? чтоб Входные данные для программы (графы) читались из файла. и оценку сложности
0
zmei89
32 / 7 / 1
Регистрация: 10.09.2010
Сообщений: 835
12.01.2012, 17:43  [ТС] #6
может из этого проекта можно что то выдернуть чтоб граф построился,или в этом проекте переделать???
0
Вложения
Тип файла: zip deikstra-algoritm.zip (193.8 Кб, 218 просмотров)
zmei89
32 / 7 / 1
Регистрация: 10.09.2010
Сообщений: 835
12.01.2012, 22:35  [ТС] #7
так как сделать чтоб граф выводился чтоб данные бли из тестового файла
0
ruslan_abel
33 / 33 / 14
Регистрация: 06.05.2011
Сообщений: 91
12.01.2012, 23:52 #8
На счет ввода из файла.
Добавьте
C++
1
#include <fstream>
Затем перед началом ввода
C++
1
ifstream input("input.txt");
И потом читайте данные из потока input вместо cin:
C++
1
input >> n;
0
zmei89
32 / 7 / 1
Регистрация: 10.09.2010
Сообщений: 835
13.01.2012, 10:59  [ТС] #9
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
#include<iostream>
#include<string.h>
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#include<clocale>
#include <fstream>
 
#define word unsigned int
 
using namespace std;
 
int i, j, n, p, xn, xk;
int flag[11];
word c[11][11], l[11];
char s[80], path[80][11];
 
int min(int n)
{
        int i, result;
        for(i=0;i<n;i++)
                if(!(flag[i])) result=i;
        for(i=0;i<n;i++)
                if((l[result]>l[i])&&(!flag[i])) result=i;
        return result;
}
 
word minim(word x, word y)
{
        if(x<y) return x;
        return y;
}
 
int main()
{
                setlocale(LC_ALL, "Russian_Russia.1251");
        cout<<"напишите число точек: ";
        cin>>n;
        for(i=0;i<n;i++)
                for(j=0;j<n;j++) c[i][j]=0;
        for(i=0;i<n;i++)
                for(j=i+1;j<n;j++)
                {
                    cout<<" задайте длины рёбер  x"<<i+1<<" do x"<<j+1<<": ";
                    cin>>c[i][j];
                }
        cout<<"   ";
        for(i=0;i<n;i++) cout<<"    X"<<i+1;
        cout<<endl<<endl;
        for(i=0;i<n;i++)
        {
                printf("X%d",i+1);
                for(j=0;j<n;j++)
                {
                        printf("%6d",c[i][j]);
                        c[j][i]=c[i][j];
                }
                printf("\n\n");
        }
        for(i=0;i<n;i++)
                for(j=0;j<n;j++)
                        if(c[i][j]==0) c[i][j]=65535; //nekonecno
        cout<<" задайте начальную точку: ";
        cin>>xn;
        cout<<" задайте конечную точку: ";
        cin>>xk;
        xk--;
        xn--;
        if(xn==xk)
        {
                cout<<"Начальная и конечные точки совпадают."<<endl;
                getch();
                return 0;
        }
 
        for(i=0;i<n;i++)
        {
                flag[i]=0;
                l[i]=65535;
        }
        l[xn]=0;
        flag[xn]=1;
        p=xn;
        itoa(xn+1,s,10);
                for(i=1;i<=n;i++)
                {
                        strcpy(path[i],"X");
                        strcat(path[i],s);
                }
                do
                {
                        for(i=0;i<n;i++)
                                if((c[p][i]!=65535)&&(!flag[i])&&(i!=p))
                                {
                                        if(l[i]>l[p]+c[p][i])
                                        {
                                                itoa(i+1,s,10);
                                                strcpy(path[i+1],path[p+1]);
                                                strcat(path[i+1],"-X");
                                                strcat(path[i+1],s);
                                        }
                                        l[i]=minim(l[i],l[p]+c[p][i]);
                                }
                        p=min(n);
                        flag[p]=1;
                }
                while(p!=xk);
        if(l[p]!=65535)
        {
                cout<<"Put: "<<path[p+1]<<endl;
                cout<<"Dlina puti: "<<l[p]<<endl;
        }
        else
                cout<<"Путь не существует!"<<endl;
        getch();
        return 0;
}


а куда добавить
ifstream input("input.txt");
input >> n; не пойму не как
0
13.01.2012, 10:59
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.01.2012, 10:59
Привет! Вот еще темы с решениями:

Алгоритм Дейкстры
Всем доброго дня! Столкнулся с проблемой, никак не могу понять, как лучше...

Алгоритм Дейкстры
Ребятушки, помогите, пожалуйста. Нужна реализация алгоритма дейкстры на...

Алгоритм Дейкстры
Здравствуйте!!! Есть код для нахождения длин от начальной вершины до всех...

Алгоритм Дейкстры
Помогите найти ошибку плз. Первый шаг алгоритма выполняет правильно,а...


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

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

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