Практикум по курсу "Алгоритмизация и программирование". Часть 2. Андрианова А.А - 117 стр.

UptoLike

ВУЗ: 

КФУ | Казань

Составители: 

Рубрика: 

. Практикум по курсу «Алгоритмизация и программирование». Часть 2
jj=j;
f=1; break;
}
}
if(f==1)
{
// если перешли в очередную вершину пути,
// запоминаем ее номер в v и указываем,
// что смежные вершины будем искать,
// начиная с нулевой вершины
v=jj; jj=-1;
}
else
{
// не нашли смежных непомеченных вершин,
// осуществляем возврат в предыдущую вершину
jj=v; // сохраняем номер текущей вершины,
// чтобы продолжить поиск смежных
// вершин со следующей за ней
if(PopStack(st,v)!=-1)
{
// извлекли из стека предшествующую
// вершину и поместили ее номер в v,
// с прежней вершины jj снимаем пометку
x[jj]=0;
k--;
sum-=g.a[v][jj];
}
else
// стек оказался пустым, т.е. были
// просмотрены все возможные варианты,
// осуществляем выход из цикла
break;
}
}
}
Задача 4. Дан взвешенный граф в виде матрицы смежности. Найти крат-
чайший путь между двумя заданными вершинами (s – начальная вершина, t
– конечная вершина).
Одним из самых известных алгоритмов решения данной задачи является
алгоритм Дейкстра (1959 г.).
Кратчайший путь будет представлен с помощью двух массивов T и H.
T[v] – длина кратчайшего пути от начальной вершины к v, H[v] – вершина,
117
             .       Практикум по курсу «Алгоритмизация и программирование». Часть 2
                                 jj=j;
                                 f=1; break;
                           }
                      }
                 if(f==1)
                 {
                      // если перешли в очередную вершину пути,
                      // запоминаем ее номер в v и указываем,
                      // что смежные вершины будем искать,
                      // начиная с нулевой вершины
                      v=jj; jj=-1;
                 }
                 else
                 {
                      // не нашли смежных непомеченных вершин,
                      // осуществляем возврат в предыдущую вершину
                      jj=v;   // сохраняем номер текущей вершины,
                             // чтобы продолжить поиск смежных
                             // вершин со следующей за ней
                      if(PopStack(st,v)!=-1)
                      {
                           // извлекли из стека предшествующую
                           // вершину и поместили ее номер в v,
                           // с прежней вершины jj снимаем пометку
                           x[jj]=0;
                           k--;
                           sum-=g.a[v][jj];
                      }
                      else
                           // стек оказался пустым, т.е. были
                           // просмотрены все возможные варианты,
                           // осуществляем выход из цикла
                           break;
                 }
         }
   }

    Задача 4. Дан взвешенный граф в виде матрицы смежности. Найти крат-
чайший путь между двумя заданными вершинами (s – начальная вершина, t
– конечная вершина).
    Одним из самых известных алгоритмов решения данной задачи является
алгоритм Дейкстра (1959 г.).
    Кратчайший путь будет представлен с помощью двух массивов T и H.
T[v] – длина кратчайшего пути от начальной вершины к v, H[v] – вершина,

                                      117

Страницы