Алгоритм Дейкстры, использующий метки

В рассматриваемой реализации данного алгоритма массив h[1..n] является массивом меток: метка h[i]=0, если построение кратчайшего пути из вершины s в вершину i не завершено, и h[i]=1 в противном случае.

<span style="color: #0000ff;">void LDG_DIJKSTRA_H(int n,int s)</span>
<span style="color: #0000ff;">{</span>
<span style="color: #0000ff;">int i, nq , c,k;</span>
<span style="color: #0000ff;">int jq = 0 ,j = 0;</span>
<span style="color: #0000ff;">vtype* p ;</span>
<span style="color: #0000ff;"> </span>
<span style="color: #0000ff;">for(i = 0 ; i  &lt; n ;++i)</span>
<span style="color: #0000ff;">{</span>
<span style="color: #0000ff;">up[i] = 0 ;</span>
<span style="color: #0000ff;">dist[i] = MAX ;</span>
<span style="color: #0000ff;">h[i] = 0 ;</span>
<span style="color: #0000ff;">name[i] = i ;</span>
<span style="color: #0000ff;">}</span>
<span style="color: #0000ff;">dist[s] = 0 ;</span>
<span style="color: #0000ff;">nq = n - 1;</span>
<span style="color: #0000ff;">while(nq &gt;= 0)</span>
<span style="color: #0000ff;">{</span>
<span style="color: #0000ff;">c = 0 ;</span>
<span style="color: #0000ff;">while(h[c]!=0) ++c ;</span>
<span style="color: #0000ff;">i = c ;</span>
<span style="color: #0000ff;">for(k = c; k &lt; n ; ++k)</span>
<span style="color: #0000ff;">if(h[k] == 0)</span>
<span style="color: #0000ff;">if(dist[i] &gt; dist[k])</span>
<span style="color: #0000ff;">i = k ;</span>
<span style="color: #0000ff;"> </span>
<span style="color: #0000ff;">h[i] = 1 ;</span>
<span style="color: #0000ff;">--nq ;</span>
<span style="color: #0000ff;"> </span>
<span style="color: #0000ff;">p = ADJ[i] ;</span>
<span style="color: #0000ff;">while(p!= NULL)</span>
<span style="color: #0000ff;">{</span>
<span style="color: #0000ff;">j = (*p).name ;</span>
<span style="color: #0000ff;">if(h[j]==0)</span>
<span style="color: #0000ff;">if(dist[j]&gt;(dist[i] + (*p).w))</span>
<span style="color: #0000ff;">{</span>
<span style="color: #0000ff;">dist[j] = dist[i] + (*p).w ;</span>
<span style="color: #0000ff;">up[j] = i ;</span>
<span style="color: #0000ff;">}</span>
<span style="color: #0000ff;">p = (*p).next ;</span>
<span style="color: #0000ff;">}</span>
<span style="color: #0000ff;">}</span>
<span style="color: #0000ff;">p = NULL ;</span>
<span style="color: #0000ff;">delete p ;</span>
<span style="color: #0000ff;">};</span>

Здесь

Name – массив имен

Dist – массив кратчайших расстояний до вершин

up – массив вершин, являющихся предпоследними в построенном кратчайшем пути

h – массив меток

nq – текущее количество непросмотренных вершин графа

n- общее количество вершин графа

s – вершина от которой ищем расстояния

Данный алгоритм имеет оценку сложности O(n2).  Внешний цикл выполняется n раз (по всем вершинам), а на нахождение минимума во внутреннем цикле тратится порядка n операций.

Оставить комментарий

Вы должны быть зарегистрированы чтобы комментировать.