Графы (кратчайший путь и обход ВСЕХ вершин)

[08ekhiv1]

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

Разумно ли здесь использовать алгоритм Дейкстры? (Если да, то каким образом и совместно с каким алгоритмом обхода ВСЕХ вершин и возврата в начальную вершину.)

Заранее спасибо...

[ArtInt]

Можно поподробнее. Под обходом ВСЕХ вершин наверное имелось ввиду выяснение какие вершины будут пройдены для того чтобы из вершины A попасть в вершину B кратчайшим путем. Если здесь учитываются весы графа(грани это например километры), то Дейкстра предпочтительнее, если просто наименьшее количество вершин то поиск в глубину.
Кстати про графы отвечал также в данной теме
http://programmersforum.ru/showthread.php?t=46211

[08ekhiv1]

Вот то в том и дело... Что мне не надо пройти из вершины А в вершину В. Впринципе надо. Просто дело в том что вершина А и явлется вершиной В. Мне надо пройти ВСЕ вершины графа кратчайшим путем и вернуться в вершину А, т.е. ту с которой начал... Помоему в условии я ясно изложился.

[ArtInt]

Это называется эйлеров цикл.
Вот например, как отвечали на данный вопрос на форуме worldok.ru

Эйлеровым путем в графе называется произвольный путь, проходящий через каждое ребро графа в точности один раз.
Замкнутый эйлеров путь называется эйлеровым обходом или эйлеровым циклом.
Эйлеров граф — граф, в котором существует эйлеров обход.
Критерий эйлеровости графа: «Эйлеров обход в графе существует тогда и только тогда, когда граф связный и все его вершины четной степени».
Нахождение эйлерова цикла можно выполнить эффективно, с помощью алгоритма, основная идея которого содержиться в построении произвольных замкнутых циклов (если вы окажетесь в эйлеровом графе, и будете идти произвольно по его ребрам, сжигая их после своего прохода, то рано или поздно вы вернетесь в точку старта), и обьединении таких циклов в единый эйлеров цикл.

Вот пример исходника, моделирующего Эйлеров граф:
Код

Program Euler;
const n=9;
      m: array[1..n, 1..n] of boolean=
      (
      (False, True,  True,  False, False, False, False, False, False),
      (True,  False, True,  False, False, False, True,  True,  False),
      (True,  True,  False, True,  True,  False, False, False, False),
      (False, False, True,  False, True,  False, False, False, False),
      (False, False, True,  True,  False, True,  False, True,  False),
      (False, False, False, False, True,  False, True,  True,  True ),
      (False, True,  False, False, False, True,  False, True,  True ),
      (False, True,  False, False, True,  True,  True,  False, False),
      (False, False, False, False, False, True,  True,  False, False)
      );
Type
    list=^node;
    node=record
             i: integer;
          next: list
         end;
Var stack1, stack2: list;
        v, u, x, i: integer;

Procedure Push(x: integer; var stack: list);
Var temp: list;
Begin
   New(temp);
   temp^.i:=x;
   temp^.next:=stack;
   stack:=temp
End;

Procedure Pop(var x: integer; var stack: list);
Begin
   x:=stack^.i;
   stack:=stack^.next
End;

Function Peek(stack: list): integer;
Begin
   Peek:=stack^.i
End;

Procedure PrintList(l: list);
Begin
   Writeln;
   If l=nil then writeln('NIL');
   While l<>nil do
   Begin
     Write(l^.i:3);
     l:=l^.next
   End
End;

Begin
  stack1:=nil;
  stack2:=nil;
  Write('Начальная вершина: ');readln(v);
  Push(v, stack1);
  While stack1<>NIL do
  Begin
    v:=peek(stack1);
    i:=1;
    While (i<=n) and not m[v, i] do inc(i);
    If i<=n then
            Begin
              u:=i;
              Push(u, stack1);
              m[v, u]:=False;
              m[u, v]:=False;
            End
            else
            Begin
              pop(x, stack1);
              push(x, stack2)
            End
  End;
  PrintList(stack2)
End

Также можно посмотреть задачу комивояжера

[aghasalim]

mojet kto-nibud perevesti eto na Java

[bondik]

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

//Алгоритм Дейкстры.поиска кратчайшего пути
#include <vcl.h>
#include <iostream.h>
#include <conio.h>
#pragma hdrstop
#pragma argsused

#define VERTEXES 6	//Число вершин в графе

int v;
int main(int argc, char* argv[])
{
   clrscr();
   int infinity=1000;                     // Бесконечность
   int p= VERTEXES;				// Количество вершин в графе
   int a[VERTEXES][VERTEXES]={ 0,1,0,0,1,3,  // Матрица смежности графа
                               1,0,5,0,0,1,
                               0,5,0,5,20,1,
     	                         0,0,5,0,3,2,
                               1,0,20,3,0,10,
                               3,1,1,2,10,0  };

   // Будем искать путь из вершины s в вершину g
   int s;              		// Номер исходной вершины
   int g;              		// Номер конечной вершины
   cout<<"Введите s: ";  	// Номер может изменяться от 0 до p-1
   cin>>s;
   cout<<"Введите g: ";
   cin>>g;
   int x[VERTEXES]; //Массив, содержащий единицы и нули для каждой вершины,
                  // x[i]=0 - еще не найден кратчайший путь в i-ю вершину,
                  // x[i]=1 - кратчайший путь в i-ю вершину уже найден
   int t[VERTEXES];  //t[i] - длина кратчайшего пути от вершины s в i
   int h[VERTEXES];  //h[i] - вершина, предшествующая i-й вершине
   		         // на кратчайшем пути

   // Инициализируем начальные значения массивов
   int u;		    // Счетчик вершин
   for (u=0;u<p;u++)
   {
      t[u]=infinity; //Сначала все кратчайшие пути из s в i 
	//равны бесконечности
      x[u]=0;        // и нет кратчайшего пути ни для одной вершины
   }
   h[s]=0; // s - начало пути, поэтому этой вершине ничего не предшествует
   t[s]=0; // Кратчайший путь из s в s равен 0
   x[s]=1; // Для вершины s найден кратчайший путь
   v=s;    // Делаем s текущей вершиной
   
   while(1)
   {
      // Перебираем все вершины, смежные v, и ищем для них кратчайший путь
      for(u=0;u<p;u++)
      {
         if(a[v][u]==0)continue; // Вершины u и v несмежные
         if(x[u]==0 && t[u]>t[v]+a[v][u]) //Если для вершины u еще не 
	//найден кратчайший путь
            	// и новый путь в u короче чем 
	//старый, то
         {
            t[u]=t[v]+a[v][u];	//запоминаем более короткую длину пути в
	//массив t и
            h[u]=v;	//запоминаем, что v->u часть кратчайшего 
	//пути из s->u
         }
      }

      // Ищем из всех длин некратчайших путей самый короткий
      int w=infinity;  // Для поиска самого короткого пути
      v=-1;            // В конце поиска v - вершина, в которую будет 
                       // найден новый кратчайший путь. Она станет 
                       // текущей вершиной
      for(u=0;u<p;u++) // Перебираем все вершины.
      {
         if(x[u]==0 && t[u]<w) // Если для вершины не найден кратчайший 
                               // путь и если длина пути в вершину u меньше
                               // уже найденной, то
         {
            v=u; // текущей вершиной становится u-я вершина
            w=t[u];
         }
      }
      if(v==-1)
      {
         cout<<"Нет пути из вершины "<<s<<" в вершину "<<g<<"."<<endl;
         break;
      }
      if(v==g) // Найден кратчайший путь,
      {        // выводим его
         cout<<"Кратчайший путь из вершины "<<s<<" в вершину "<<g<<":";
   	   u=g;
   	   while(u!=s)
         {
            cout<<" "<<u;
            u=h[u];
         }
         cout<<" "<<s<<". Длина пути - "<<t[g];
   	   break;
      }
      x[v]=1;
   }
   getch();
}
/*Программа запрашивает вершины s и q и выводит кратчайший путь. Например, после ввода s = 3, q = 6, программа выводит 

Нет пути из вершины 3 в вершину 6. 

После ввода s = 0, q = 2 программа выводит 

Кратчайший путь из вершины 0 в вершину 2: 2 5 1 0. Длина пути = 3.*/

//---------------------------------------------------------------------------