Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.91/97: Рейтинг темы: голосов - 97, средняя оценка - 4.91
5 / 5 / 2
Регистрация: 04.06.2009
Сообщений: 147

Алгоритм Дейкстры, нахождение кратчайшего пути

13.04.2011, 22:32. Показов 18765. Ответов 19
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Доброго времени суток всем!
У меня вопрос. Написала программку для нахождения кратчайшего пути (алгоритм Дейкстра), но мне надо её как то по приличней оформить, т.е.
можно как то визуализовать результат так, чтобы, к примеру, после того как прога подсчитает результат, рисовался бы граф и этот самый короткий путь, который посчитала программа? Как это сделать и с чего начать?
Вот код работы :
Код:
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();
}
1
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
13.04.2011, 22:32
Ответы с готовыми решениями:

Нахождение кратчайшего пути в графе, алгоритм Уоршелла
Привет всем! алгоритм уоршелла, нужно найти кратчайший путь в графе. ввожу матрицу 0 1 5 1 0 2 5 2 0 работает нормально, все...

Определение кратчайшего пути алгоритмом Дейкстры
Разработка программного комплекса для определения кратчайшего пути алгоритмом Дэйстри. Программный комплекс решает задачу поиска самого...

Нахождение кратчайшего пути
Нужно сделать программу,чтоб она находила кратчайший путь от города 1 до города 2 на карте. Как реализовать в коде не знаю, помогите. ...

19
 Аватар для IrineK
2023 / 1641 / 425
Регистрация: 23.02.2011
Сообщений: 6,002
Записей в блоге: 25
13.04.2011, 23:03
При визуализации вам необходимо каждый пункт задавать двумя координатами. Тут возникает вопрос истинных значений ребер.
Допустим, у вас четыре пункта. Четырехугольник с данными любыми ребрами и то не всегда нарисуешь (какое-то - слишком длинное, или слишком короткое). А тут еще и диагонали...
0
186 / 186 / 21
Регистрация: 08.01.2011
Сообщений: 1,139
13.04.2011, 23:36
Проще всего реализовать алгоритм Флойда для на нахождения кратчайшего пути и матрицу Ху для нахождения вершин, через которые проходит этот кратчайший путь.
0
5 / 5 / 2
Регистрация: 04.06.2009
Сообщений: 147
14.04.2011, 12:37  [ТС]
Зачем мне делать алгоритм флойда, ели у меня уже есть готовый дейкстры(тем более моё задание именно в том, чтобы сделать именно дейкстру). мой алгоритм как раз и выводит матрицу пути и кратчайший путь к нему, но нужно, что бы он непосредственно рисовал картинку...
0
 Аватар для IrineK
2023 / 1641 / 425
Регистрация: 23.02.2011
Сообщений: 6,002
Записей в блоге: 25
14.04.2011, 16:16
Рисовать по ребрам нужно треугольниками.
Допустим, у нас четыре пункта.
Х1Х2 = 5 - изображаем (с масштабным множителем, скажем 20*5=100)
Х1Х3 = 7 и Х2Х3 = 4 - точка Х3 - пересечение двух окружностей (с центром Х1 и радиусом 7, с центром Х2 и радиусом 4).
Х1Х4 = 4 и Х3Х4 = 3 - точка Х4 - пересечение двух окружностей (с центром Х1 и радиусом 4, с центром Х3 и радиусом 3).

Если пунктов у нас больше, процесс продолжается.

Возникают жесткие требования к ребрам - они должны иметь такие величины, чтобы все построения были возможными. Что попало уже не наберешь.

Добавлено через 10 минут
Укажите, в чем вы пишите. Возможно, в чем умеете рисовать.
0
5 / 5 / 2
Регистрация: 04.06.2009
Сообщений: 147
14.04.2011, 18:17  [ТС]
я пишу в С++, но я новичок и рисовать умею, только матлабе и др. математических программх, т.к. занимаюсь в основном расчётами в матлабе...
Но эту работу сделать обязательно, предмет такой, хочу я или не хочу...
0
 Аватар для IrineK
2023 / 1641 / 425
Регистрация: 23.02.2011
Сообщений: 6,002
Записей в блоге: 25
14.04.2011, 18:49
я пишу в С++
Компилятор? Ось?
0
5 / 5 / 2
Регистрация: 04.06.2009
Сообщений: 147
14.04.2011, 22:56  [ТС]
Borland C++
MS Visual Studio
0
108 / 108 / 23
Регистрация: 21.03.2010
Сообщений: 445
14.04.2011, 23:07
Цитата Сообщение от Karta Посмотреть сообщение
я пишу в С++, но я новичок и рисовать умею, только матлабе и др. математических программх, т.к. занимаюсь в основном расчётами в матлабе...
Но эту работу сделать обязательно, предмет такой, хочу я или не хочу...
у меня один знакомый с работы на Qt перешел. До этого прогал на матлабе и чистом си, пришлось правда разбираться с классами но за неделю справился. там можно рисовать без особых проблем. . .
+ в матлаб можно вернуть то что посчитано на си.
0
5 / 5 / 2
Регистрация: 04.06.2009
Сообщений: 147
14.04.2011, 23:40  [ТС]
Но мне нельзя использовать матлаб, надо всё сделать либо в с++ либо с помощью графвиз...
0
108 / 108 / 23
Регистрация: 21.03.2010
Сообщений: 445
14.04.2011, 23:44
Цитата Сообщение от Karta Посмотреть сообщение
всё сделать либо в с++
тогда рекомендую Qt, её осваивать весьма нетрудно. чтобы нарисовать там что-то нужно разобраться только с одним классом и общими принципами. Есть переведённые книжки по Qt(их основных 2), и всё остальное чтобы можно было без проблем что-нибудь сварить за вечер то же есть...
1
5 / 5 / 2
Регистрация: 04.06.2009
Сообщений: 147
17.04.2011, 00:56  [ТС]
"тогда рекомендую Qt" а что это такое? Не слышала...
0
108 / 108 / 23
Регистрация: 21.03.2010
Сообщений: 445
17.04.2011, 03:11
ну вообще говоря в википедии написано но это кроссплатформенная среда разработки графических интерфейсов. состоит чуть менее чем полностью из чистого с++, но он немного расширен. у них есть своя программка разработки и она не плоха, но можно накрутить qt на visual studio(хоть и с проблемами). есть даже интерфейс для создания приложений, но мастера кунг-фу им не пользуются.
1
 Аватар для IrineK
2023 / 1641 / 425
Регистрация: 23.02.2011
Сообщений: 6,002
Записей в блоге: 25
17.04.2011, 04:20
Начертить многоугольник с разноцветными диагоналями (подсвечивая путь) можно и в консоли.
Осваивать новые технологии не нужно. Все довольно просто.
Например, можете посмотреть: Рисование линий по координатам

Что нужно, так это продумать алгоритм черчения. Как я уже говорила, нужно чертить треугольниками, веером по часовой стрелке. В сети есть решения.
Будет время - я тоже посмотрю. но обещать не могу - полный завал на работе О_о.
1
║XLR8║
 Аватар для outoftime
1212 / 909 / 270
Регистрация: 25.07.2009
Сообщений: 4,360
Записей в блоге: 5
17.04.2011, 05:17
Karta, Нарисуй картинку и сохрание ее, к примеру, в формате jpeg.
0
5 / 5 / 2
Регистрация: 04.06.2009
Сообщений: 147
21.04.2011, 12:16  [ТС]
Доброго дня!! мне нужно вывод моей программы( граф, который получается) скинуть в отдельный текстовый файл, но как я не стараюсь у меня почему то, скидывается в отдельный файл код программы а не её вывод... Как это модно исправить?
0
║XLR8║
 Аватар для outoftime
1212 / 909 / 270
Регистрация: 25.07.2009
Сообщений: 4,360
Записей в блоге: 5
21.04.2011, 14:38
Цитата Сообщение от Karta Посмотреть сообщение
но как я не стараюсь у меня почему то, скидывается в отдельный файл код программы а не её вывод
Покажи код, который выводит сам себя, мне ооочень интересно (:
0
5 / 5 / 2
Регистрация: 04.06.2009
Сообщений: 147
21.04.2011, 14:56  [ТС]
я просто понять никак не могу в чём проблема, в учебниках и видео уроках ясно говорят как сделать запись в файл, у меня же выдаёт ошибки и никуда ничего не записывает, не смотря на элементарный пример...
0
5 / 5 / 2
Регистрация: 04.06.2009
Сообщений: 147
21.04.2011, 15:00  [ТС]
вот что получается...
Вложения
Тип файла: rar gr.rar (2.3 Кб, 247 просмотров)
0
 Аватар для aiwprton805
78 / 77 / 51
Регистрация: 30.03.2013
Сообщений: 194
06.11.2013, 00:14
А можешь скинуть ещё раз код, только подробные комментарии написать, что там творится?)
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
06.11.2013, 00:14
Помогаю со студенческими работами здесь

Нахождение кратчайшего пути, поиск с возвратом
Описание проблемы: Есть матрица MxN, на матрицы есть дом школьника и школа. Школьник может двигаться в 4 направления. На прохождения 1ой...

Графы: нахождение кратчайшего пути между вершинами
Алгоритм фронт фолны в графе Помогите.. Дана матрица Ag (Матрица смежности графа) И координаты начальной вершины i,j и кординаты...

Нахождение кратчайшего пути от одной вершины графа до другой
Парни помогите доделать , в общем дан граф , я представил его связи в виде матрицы смежностей #include &lt;iostream.h&gt; #include...

Вывод пути (алгоритм Дейкстры)
Реализация алгоритма Дейкстра. В массиве distance - найденные кратчайшие пути, visited - логический, для хранения информации о...

Нахождение кратчайшего пути в неорентированном графе от заданой вершины к заданной
Добрый день. Вот решаю задачку о кратчайщем расстояние между двумя верщинами в неорентированном связном графе без циклов. Заданны такие...


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

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Новые блоги и статьи
SDL3 для Web (WebAssembly): Работа со звуком через SDL3_mixer
8Observer8 08.02.2026
Содержание блога Пошагово создадим проект для загрузки звукового файла и воспроизведения звука с помощью библиотеки SDL3_mixer. Звук будет воспроизводиться по клику мышки по холсту на Desktop и по. . .
SDL3 для Web (WebAssembly): Основы отладки веб-приложений на SDL3 по USB и Wi-Fi, запущенных в браузере мобильных устройств
8Observer8 07.02.2026
Содержание блога Браузер Chrome имеет средства для отладки мобильных веб-приложений по USB. В этой пошаговой инструкции ограничимся работой с консолью. Вывод в консоль - это часть процесса. . .
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве
8Observer8 02.02.2026
Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .
Философия технологии
iceja 01.02.2026
На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .
SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf
8Observer8 01.02.2026
Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .
SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли
8Observer8 30.01.2026
Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm
8Observer8 30.01.2026
Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .
SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров
8Observer8 29.01.2026
Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru