Алгоритм Дейкстры. Реализация на очереди С++.

Алгоритм Дейкстры предназначен для нахождения расстояния в графе.
Суть данного алгоритма заключается в том, что выбирается вершина, имеющая минимальное расстояние до заданной стартовой вершины, потом производится ослабление всех исходящих ребер.
Алгоритм:

1. INITIALIZE_SINGLE_SOURCE(G,S)
2. S=0
3. Q=V[s] //добавляем стартовую вершину в очередь с приоритетом
4. While(!Q.empty()) //пока очередь не пуста
1. u=Extract_Min(Q) //берем вершину из очереди с минимальным расстоянием
2. for v из Adj[u] //для любой смежной вершины v к u
1. Relax (u,v,w) //производим релаксацию ребра

Процесс релаксации описан в алгоритме Форда-Беллмана:

Форд-Беллман

Реализация:

 
void Dijkstra_Shortest_Path(unsigned NumOfVertices, unsigned start){
int M [5][5] = {{0,6,0,7,0}, {0,0,5,8,-4}, {0,-2,0,0,0},{0,0,-3,0,9},{2,0,7,0,0}};
priority_queue< pair< unsigned int,double>, vector< pair > , Prioritize > Q;    
    int u,v,w;
    vector< double> d(NumOfVertices,INFINITY);
    d[start] = 0;
    Q.push(pair< unsigned int,double >(start,d[start]));
    while(!Q.empty())
    {
        u = Q.top().first;
    final.push(u);
        Q.pop();
        for(int v = 0 ; v < NumOfVertices ; v++)
        {
   if (M[u][v]) {
            w = M[u][v];
            cout< d[u] + w)
            {
                d[v] = d[u] + w;
                Q.push(pair(v,d[v]));
            }
   }
        }
    }
    for(int i=0; i< NumOfVertices; i++) 
   cout< <"Vertex "< < i< <" cost of vertex: "< < d[i]< < endl;
}

Для того, чтобы добавление в очередь с приоритетом работало, то есть сортировалось в процессе добавления пары, нужно сделать класс-компаратор и перегрузить оператор <

 
class Prioritize
{
public:
    int operator() ( const pair& p1, const pair& p2 )
    {
        return p1.second < p2.second;
    }
};

Posted in: Алгоритмы, Графы, CPP