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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

. Практикум по курсу «Алгоритмизация и программирование». Часть 2
нимальным элементом массива T среди тех, которые соответствуют непоме-
ченным вершинам, является Т[6]=12. Поскольку вершина 6 – конечная вер-
шина, то задача решена.
Таким образом, длина кратчайшего пути из вершины 1 в вершину 6 равна
12 (T[6]).
// определение функции поиска кратчайшего пути
// между двумя вершинами с помощью алгоритма Дейкстра
int Dijkstra(Graph2& g, int s, int t, int* H, int* T)
{
// создание вспомогательного массива пометок
int* X=new int[g.n];
int flag,i,m,u,
v=s-1; // номер текущей вершины
// начальная инициализация массива пометок X и массива
// длин кратчайших путей T
for(i=0;i<g.n;i++)
{
T[i]=MAX_INT;
X[i]=0;
}
// инициализация элементов массивов для начальной
// вершины s
H[s-1]=0;
T[s-1]=0;
X[s-1]=1;
while(true)
{
// цикл поиска непомеченных вершин,
// смежных с s-ой вершиной
for(u=0;u<g.n;u++)
if(g.a[v][u]!=0 && g.a[v][u]!=MAX_INT)
{
// корректировка длин кратчайших путей
// происходит, если путь из вершины s
// в вершину u, проходящий через
// вершину v, будет короче, чем прежний
if(X[u]==0 && T[u]>T[v]+g.a[v][u])
{
T[u]=T[v]+g.a[v][u];
H[u]=v+1;
}
}
121
            .       Практикум по курсу «Алгоритмизация и программирование». Часть 2
    нимальным элементом массива T среди тех, которые соответствуют непоме-
    ченным вершинам, является Т[6]=12. Поскольку вершина 6 – конечная вер-
    шина, то задача решена.


    Таким образом, длина кратчайшего пути из вершины 1 в вершину 6 равна
12 (T[6]).

   // определение функции поиска кратчайшего пути
   // между двумя вершинами с помощью алгоритма Дейкстра
   int Dijkstra(Graph2& g, int s, int t, int* H, int* T)
   {
         // создание вспомогательного массива пометок
         int* X=new int[g.n];
         int flag,i,m,u,
         v=s-1; // номер текущей вершины
         // начальная инициализация массива пометок X и массива
         // длин кратчайших путей T
         for(i=0;iT[v]+g.a[v][u])
                        {
                             T[u]=T[v]+g.a[v][u];
                             H[u]=v+1;
                        }
                   }
                                     121

Страницы