VPF::Поиск кратчайшего пути в графе

Winchester

Дата 23.5.2008, 13:19 (ссылка)

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

Загрузка ...

Новичок

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

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

у меня курсовая на данную тему.
ввод данных из файла (первая строка - количество вершин, далее как и обычная матрица) в матрицу весов. нужно найти и вывести кратчайший путь для любых двух вершин в графе если он существует. написал прогу, в которой попытался реализвовать оба эти алгоритма.
***
Алгоритм Флойда работает замечательно, всё получается... и новую матрицу вычисляет правильно и путь тоже находит верный.
может быть дадите совет как можно вывести все кратчайшие пути для данных двух вершин, т.к. и такое может быть...
***
с алгоритмом дейкстры есть небольшие сложности...
если я нахожу путь из 1 вершины во все остальные, то путь находит верный...
если путь ищу из какой-то другой вершины, то программу зацикливает... глаз замылен уже и может быть просто не вижу своей ошибки... а может быть данный алгоритм находит пути только для 1-й вершины, не знаю... поэтому тоже прошу совета...
***
мне надо сравнить время работы этих алгоритмов, как это можно сделать в СИ++ не знаю... очень прошу немного помочь мне разобраться в этом...

Код


#include<conio.h>
#include<stdio.h>
#include<stdlib.h>
#include<values.h>
#include<stdlib.h>
int start, finish, z, min;

int **matrix, **a, **p; // matrix
int node; // Number of graph nodes

int *s, *b, *c;
//---------------------------------------------------------------------------
void f1() // enter matrix
{
 int i, j;
 FILE *in=0;

// in=fopen("123456.txt", "r");
 in=fopen("ford2.txt", "r");
 fscanf(in, "%d", &node);

 puts("");
 printf("Number of nodes: %d", node);
 puts("");

 matrix=(int **) malloc(node*sizeof(int)); // allocating memory for matrix
 for (i=0; i<node; i++)
     matrix[i]=(int *) malloc(node*sizeof(int));

 for (i=0; i<node; i++) // reading matrix
     for (j=0; j<node; j++)
         {
    fscanf(in, "%d", &matrix[i][j]);
    if ( matrix[i][j]==0 ) matrix[i][j]=MAXINT;
         }


 for (i=0; i<node; i++)
     matrix[i][i]=0;

 puts("");
}
//---------------------------------------------------------------------------
void f2() // printing matrix
{
 int i, j; /*
 for (i=0; i<node; i++)
    {
     for (j=0; j<node; j++)
         if (j==0) printf("%d", matrix[i][j]);
            else printf("%3d", matrix[i][j]);
     puts("");
    }         */

 puts("");
 for (i=0; i<node; i++)
     {
      j=0;

      if (matrix[i][j]==MAXINT) printf("%4c ", '-');
         else printf("%4d ", matrix[i][j]);

      for (j=1; j<node; j++)
          if (matrix[i][j]==MAXINT) printf("%4c ", '-');
             else printf("%4d ", matrix[i][j]);

      puts("");
     }
 puts("");
}
//---------------------------------------------------------------------------
void path(int i, int j)
{

 if (p[i][j]!=i+1)
    {
     path(i, p[i][j]-1);
     printf("%d, ", p[i][j]);
    }
}
//---------------------------------------------------------------------------
void f3() // Floid Algoritm
{
 int i, j, k;

 a=(int **) malloc(node*sizeof(int));
 for (i=0; i<node; i++)
     a[i]=(int *) malloc(node*sizeof(int));

 p=(int **) malloc(node*sizeof(int));
 for (i=0; i<node; i++)
     p[i]=(int *) malloc(node*sizeof(int));

 for (i=0; i<node; i++)
     for (j=0; j<node; j++)
         {
          a[i][j]=matrix[i][j];
          p[i][j]=i+1;
         }

 for (k=0; k<node; k++)
     for (i=0; i<node; i++)
         for (j=0; j<node; j++)
             {
              long tmp;
              tmp=(long)a[i][k]+a[k][j];

              if (tmp<a[i][j])
                 {
                  a[i][j]=tmp;
                  p[i][j]=k+1;
                 }
             }

 for (i=0; i<node; i++)
     {
      for (j=0; j<node; j++)
          if (a[i][j]==MAXINT) printf("%6c", '-');
             else printf("%6d", a[i][j]);
      puts("");
     }
 puts("");

 for (i=0; i<node; i++)
     {
      for (j=0; j<node; j++)
          printf("%6d", p[i][j]);
      puts("");
     }


 printf("Enter start point: ");
 scanf("%d", &start);
 printf("Enter end point: ");
 scanf("%d", &finish);
 start--;
 finish--;
 if ( a[start][finish]==MAXINT ) printf("there is no path\n");
    else if (finish==start) printf("start and end points are the same!\n");
             else
            {
             printf("\nMinimum Path from %d to %d = %d\n", start+1, finish+1, a[start][finish]);
             printf("%d, ", start+1);
             path(start, finish);
             printf("%d", finish+1);
             puts("");
            }
 puts("");
}
//---------------------------------------------------------------------------
void path1()
{
 printf("%d <- ", finish+1);
 z=c[finish];
 while (z!=0)
        {
         printf("%d <- ", z+1);
         z=c[z];
        }
 printf("%d <- start", start+1);
 puts("");
}
//---------------------------------------------------------------------------
int check()
{
 int f=node;
 for (int i=0; i<node; i++)
     if (s[i]) f--;
 return f;
}
//---------------------------------------------------------------------------
void f4() // Edsger Wybe Dijkstra Algoritm
{
 int i, j, k;

 s=(int *) malloc(node*sizeof(int));
 c=(int *) malloc(node*sizeof(int));
 b=(int *) malloc(node*sizeof(int));

 for (i=0; i<node; i++)
     s[i]=0;

 printf("\nEnter start point: ");
 scanf("%d", &start);
 printf("Enter end point: ");
 scanf("%d", &finish);
 start--; finish--;

 for (i=0; i<node; i++)
     c[i]=start;

 s[start]=1; c[start]=0;
 for (i=0; i<node; i++)
     b[i]=matrix[start][i];

 while (check())
        {
         min=MAXINT;
         for (i=0; i<node; i++)
             if (s[i]==0)
                if (b[i]<min)
                  {
                    min=b[i];
                    j=i;
                  }
         s[j]=1;

         for (k=0; k<node; k++)
             if (s[k]==0)
                {
                 long tmp;
                 tmp=(long)b[j]+matrix[j][k];
                 if (tmp<b[k])
                  {
                    b[k]=tmp;
                    c[k]=j;
                  }
                 }
        }

 /*
 printf("%6d\n", min);
 for (i=0; i<node; i++)
     printf("%6d", s[i]);
 puts("");

 for (i=0; i<node; i++)
     printf("%6d", b[i]);
 puts("");


                                */

 for (i=0; i<node; i++)
     printf("%6d", c[i]+1);
 puts("");


 if (b[finish]==MAXINT) printf("There is no path\n");
 else
      {
        printf("Minimum path from %d to %d = %d\n", start+1, finish+1, b[finish]);
        if (start==finish) printf("start and end points are the same!!!");
        else if (c[finish]==0) printf("%d <- %d <- start", start+1, finish+1);
              else path1();
      }

 puts("");
}
//---------------------------------------------------------------------------
int menu()
{
 int a;
 while (1){
              printf("Menu:\n");
              printf("1 - Input Matrix\n");
              printf("2 - Output Matrix\n");

              printf("3 - Floid Algoritm\n");
              printf("4 - Dijkstra Algoritm\n");

              printf("9 - Clear Screen\n");
              printf("0 - Exit Program\n");

              printf("Select: ");
              scanf("%d", &a);

              switch (a) {
                              case 0: return 0;
                              case 1: f1(); break;
                              case 2: f2(); break;
                              case 3: f3(); break;
                              case 4: f4(); break;
                              case 9: clrscr(); break;
                              default: printf("Wrong character!!!\n");
                             }
             }
}
//---------------------------------------------------------------------------
 main()
{
 clrscr();
 menu();
 return 0;
}

вот пара текстовых файлов с которыми я работал

Код


13
0 2 4 6 0 0 0 0 0 0 0 0 0 
0 0 1 0 0 0 7 0 0 0 0 0 0
0 0 0 2 0 0 6 0 0 0 0 0 0
0 0 0 0 5 3 0 0 0 0 0 0 0
0 0 0 0 0 0 0 9 0 3 0 0 0
0 0 0 0 2 0 5 0 0 0 0 0 0
0 0 0 0 0 0 0 10 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 5 0
0 0 0 0 0 0 0 2 0 0 9 0 0
0 0 0 0 0 0 0 0 2 0 10 0 0
0 0 0 0 0 0 0 0 0 0 0 0 4
0 0 0 0 0 0 0 0 0 0 2 0 8
0 0 0 0 0 0 0 0 0 0 0 0 0

Код


8
0 3 4 7 0 0 0 0
0 0 1 0 5 11 8 0
0 0 0 2 7 10 0 0
0 0 0 0 2 8 0 12
0 0 0 0 0 5 2 10
0 0 0 0 0 0 0 4
0 0 0 0 0 3 0 8
0 0 0 0 0 0 0 0

Это сообщение отредактировал(а) Winchester - 23.5.2008, 13:21

rrrFer

Дата 23.5.2008, 13:58 (ссылка)

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

Загрузка ...

Бывалый

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

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

Winchester,

Цитата

мне надо сравнить время работы этих алгоритмов, как это можно сделать в СИ++ не знаю

с алгоритмом разбираться не охото, но со временем можно так:

Код


#include <time.h>
#include <stdio.h>
void f3(){/*...*/}
void f4(){/*...*/}
int menu(){
    int a;
    time_t t1,t2;
    while (1){
        printf("Menu:\n");
        //...
        printf("3 - Floid Algoritm\n");
        printf("4 - Dijkstra Algoritm\n");
        //...
        printf("Select: ");
        scanf("%d", &a);
        switch (a){
            //...
            case 3: 
                time(&t1);
                f3(); 
                time(&t2);
                printf("work time: %d\n",difftime(t2,t1));
            break;
            case 4: 
                time(&t1);
                f4(); 
                time(&t2);
                printf("work time: %d\n",int(difftime(t2,t1)));
            break;
            //...
            }
        }
}
void main(){/*...*/
    menu();
}

Это сообщение отредактировал(а) rrrFer - 23.5.2008, 13:59

esperant0

Дата 25.5.2008, 08:24 (ссылка)

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

Загрузка ...

Опытный

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

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

"может быть дадите совет как можно вывести все кратчайшие пути для данных двух вершин, т.к. и такое может быть"

Вывод всех крачайших путей превращает задачу в экспоненциальную, а по сему можно воспользоваться перебором. Перебераете ВСЕ пути, и печатаете лишь пути минимальной длины

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

Student->Teacher Assistant ->Research assistant->Microsoft Software Development Engineer

Пользователь получил наказание за то, что проигнорировал замечание которое было написано модератором а затем стерто и которое он - пользователь не мог видеть.

maxdiver

Дата 25.5.2008, 13:26 (ссылка)

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

Загрузка ...

Опытный

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

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

А если без перебора - то так: оставляем только те рёбра, которые лежат на каком-либо кратчайшем пути (ребро (a,b) веса len лежит на кратчайшем пути из s в t, если dist(s,a) + dist(b,t) + len == dist(s,t)). После чего получим граф (ориентированный, вне зависимости от того, был ли ориентирован или нет исходный граф), в котором надо найти просто все пути, что уже решается простым перебором.

Добавлено @ 13:34
Winchester

Цитата

с алгоритмом дейкстры есть небольшие сложности...
если я нахожу путь из 1 вершины во все остальные, то путь находит верный...
если путь ищу из какой-то другой вершины, то программу зацикливает... глаз замылен уже и может быть просто не вижу своей ошибки... а может быть данный алгоритм находит пути только для 1-й вершины, не знаю... поэтому тоже прошу совета...

Конечно, алгоритм Дейкстры ищет путь из любой вершины )
В коде вашем я что-то разобраться не смог, поясните хотя бы смысл трех массивов s, c, b.

А вообще - в интернете полно реализаций дейкстры, в том числе и на C. Посмотрите, может вы сами быстрее поймёте ошибку.

Это сообщение отредактировал(а) maxdiver - 25.5.2008, 13:34

Winchester

Дата 2.6.2008, 19:51 (ссылка)

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

Загрузка ...

Новичок

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

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

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

---
а алгоритмом дейкстры тоже разобрался... мой код работал только для тех случаев, когда путь из вершины во все остальные существует... у меня в цикле while для начала min=MAXINT, послеокончания работы цикла, если путь не найден, то значение не меняется и прога просто закливается и ищет путь снова... нужно было добавить всего одно условие if (min==MAXINT) break и тогда всё заработало отлично. между прочим на алголист об этом ни слова, я потом это уже понял после трасировки... и нашёл этот момент на википедии...
---
спасибо за помощь!!!

Код


while (check())
        {
         min=MAXINT;
         for (i=0; i<node; i++)
             if (s[i]==0)
                if (b[i]<min)
                  {
                    min=b[i];
                    j=i;
                  }
         [U]if (min==MAXINT) break;[/U]
         s[j]=1;
         for (k=0; k<node; k++)
             if (s[k]==0)
                {
                 long tmp;
                 tmp=(long)b[j]+matrix[j][k];
                 if (tmp<b[k])
                  {
                    b[k]=tmp;
                    c[k]=j;
                  }
                 }
        }

Это сообщение отредактировал(а) Winchester - 2.6.2008, 19:53

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