VPF::[C++| Borland C++ Builder] Алгоритм Дейкстра

XucT

Дата 13.6.2007, 14:41 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 2
Регистрация: 11.6.2007

Репутация: нет
Всего: нет

Вот дали тему для курсового по си: "Поиск оптимального маршрута в системе городов".
Данную задачу можно сделать на основе алгоритма Дейкстры, как мне посоветовали.
Описание алгоритма тут: http://ru.wikipedia.org/wiki/%D0%90%D0%BB%....BD.D0.B8.D0.B5

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

Буду очень благодарен за рабочий исходник на билдоре,т.к необходим наибольший обьём листинга для курсового, заранее спасибо.

P.S Поиском нашёл кое-что, но ничего не подходит(

Это сообщение отредактировал(а) XucT - 13.6.2007, 17:51

apook

Дата 14.6.2007, 07:35 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 794
Регистрация: 12.7.2006

Репутация: 10
Всего: 23

M
Guedda

Модератор: Пользуйтесь кнопкой "Код"!
http://forum.vingrad.ru/index.php?show_typ...howtopic=126445

---

Это сообщение отредактировал(а) apook - 14.6.2007, 10:13

--------------------

Мои руки из дуба, голова из свинца ну и пусть ...

apook

Дата 14.6.2007, 10:14 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 794
Регистрация: 12.7.2006

Репутация: 10
Всего: 23

Код


// Алгоритм Дейкстры
// нахождение наименьшего расстояяния от заданной точки 
// до всех остальных
#include<iostream.h> 
#include<conio.h> 
 
#define M ( sizeof(cities)/sizeof(cities[ 0 ]) )
#define N ( sizeof(inf)/sizeof(inf[ 0 ]) )
 
//якобы бесконечность, данное число должно быть больше
//максимального расстояния (по правилам алгоритма)
#define INFINITY 10000
//от какой точки пляшем :)
#define dance 2
 
//пункты
char cities[ ][ 50 ]={ "A", "B", "C", "D", "E", "F" };

struct
{
    char points[ 2 ][ 50 ]; //от пункта к пункту
    int distance;           //расстояние км
    }inf[ ]={
    {{ "A", "B" }, 65 },
    {{ "B", "C" }, 40 },
    {{ "C", "D" }, 60 },
    {{ "D", "E" }, 68 },
    {{ "E", "A" }, 32 },
    {{ "A", "F" }, 45 },
    {{ "B", "F" }, 25 },
    {{ "C", "F" }, 40 },
    {{ "D", "F" }, 60 },
    {{ "E", "F" }, 50 },
    };
 
struct range
{
    char *point;    //пункт
    int distance;   //расстояние от начальной точки
    };
  
int main() 
{
int i, j, c, current_distance, q, p, real_p;
char *current_city=NULL;
 
range *xr=new range[ M ];
//расстояние от стартовой точки до остальных изначально
//равно бесконечности
for( i=0; i<M; i++ )
{
    xr[ i ].point=NULL;
    xr[ i ].distance=INFINITY;
    }
//а начальная имеет значение ноль
xr[ 0 ].distance=0;
xr[ 0 ].point=cities[ dance ];
 
for( i=0, c=0, p=1; i<M; i++ )
{
    current_city=xr[ i ].point;
 
    for( j=0, real_p=1; j<N; j++ )
    {
        current_distance=xr[ i ].distance;

        if( strcmp(inf[ j ].points[ 0 ], current_city)==0
        ||  strcmp(inf[ j ].points[ 1 ], current_city)==0 )
        {
            //проверка не проверяли ли эту точку ранее
            for( q=0; q<i; q++ )
                if( strcmp(inf[ j ].points[ 0 ], xr[ q ].point)==0
                ||  strcmp(inf[ j ].points[ 1 ], xr[ q ].point)==0 )
                    break;
            if( q<i )
                continue;
 
           //-----------------------------
           //находим какая точка сейчас явл соседом с той которую
           //проверяем т.е до какой точки смотрим расстояние
           for( q=0; q<2; q++ )
              if( strcmp(inf[ j ].points[ q ], current_city)!=0 )
                  break;
 
           //i -- текущий пункт
           //p -- всего соседей(уже посещенных) 
           //real_p -- сосед текущего пункта который сейчас проверяется
           //j -- текущий отрезок
  
           for( c=0; c<p; c++ )
               if( strcmp(xr[ c ].point, inf[ j ].points[ q ])==0 )
                   break;
           if( c<p )
               real_p=c; //пункт посещался сверяться будем с ним  
           else
           {   //пункт не посещался
               xr[ p ].point=inf[ j ].points[ q ]; //запоминаем пункт
               real_p=p; //вносим свежие данные по нему
               ++p;
               }
  
           current_distance+=inf[ j ].distance;
           if( current_distance<xr[ real_p ].distance )
               //запоминаем расстояние
               xr[ real_p ].distance=current_distance;
              }
          }
      }
  
cout << endl << "---------------------" << endl
     << "Beeline from " << xr[ 0 ].point << endl;
for( q=1; q<p; q++ )
    cout << "to: " << xr[ q ].point << " = " << xr[ q ].distance << endl;

delete [] xr; 
getch();
return 0; 
}

--------------------

Мои руки из дуба, голова из свинца ну и пусть ...

XucT

Дата 14.6.2007, 11:03 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 2
Регистрация: 11.6.2007

Репутация: нет
Всего: нет

Благодарю за помощь, чуть позже выложу свой вариант алгоритма, только на Borland C++ Builder, авось кому-то понадобится.

Mad_Lamer

Дата 22.6.2007, 11:44 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 1
Регистрация: 22.6.2007

Репутация: нет
Всего: нет

Пожалуйста, ребята, этот же Алгоритм Дейкстры, только на паскале, можете поделится?

Это сообщение отредактировал(а) Mad_Lamer - 22.6.2007, 12:00

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Центр помощи \| Следующая тема »