Алгоритм Дейкстри дозволяє нам знайти найкоротший шлях між будь-якими двома вершинами графа.
Він відрізняється від мінімального кістякового дерева тим, що найкоротша відстань між двома вершинами може не включати всі вершини графа.
Як працює алгоритм Дейкстри
Алгоритм Дейкстри працює на тій підставі, що будь-який підшлях B -> D найкоротшого шляху A -> D між вершинами A і D також є найкоротшим шляхом між вершинами B і D.
Дейкстра використовував це властивість у протилежному напрямі, тобто. ми переоцінюємо відстань кожної вершини від початкової вершини. Потім ми відвідуємо кожен вузол та його сусідів, щоб знайти найкоротший підшлях до цих сусідів.
Алгоритм використовує «жадібний» підхід у тому сенсі, що ми знаходимо наступне найкраще рішення, сподіваючись, що кінцевий результат є найкращим рішенням для всього завдання.
Приклад алгоритму Дейкстри
Найпростіше почати з прикладу, а потім подумати про алгоритм.
Алгоритм Дейкстри. Псевдокод.
Нам слід зберігати відстань шляху кожної вершини. Ми можемо зберегти його в масиві розміру v, де v – кількість вершин.
Нам також хотілося б отримати найкоротший шлях, а не лише знати його довжину. Для цього ми порівнюємо кожну вершину з останньою оновленою довжиною шляху.
Як тільки алгоритм закінчено, ми можемо повернутись від вершини призначення до вихідної вершини, щоб знайти шлях.
Черга з мінімальним пріоритетом може використовуватися для ефективного отримання вершини з найменшою відстанню колії.
function dijkstra(G, S)
for each vertex V in G
distance[V] <- infinite
previous[V] <- NULL
If V != S, add V to Priority Queue Q
distance[S] <- 0
while Q IS NOT EMPTY
U <- Extract MIN from Q
for each unvisited neighbour V of U
tempDistance <- distance[U] + edge_weight(U, V)
if tempDistance < distance[V]
distance[V] <- tempDistance
previous[V] <- U
return distance[], previous[]
Код для алгоритму Дейкстри
Реалізація алгоритму Дейкстри у C++ наведена нижче. Складність коду може бути покращена, але абстракції зручні для зв'язку коду з алгоритмом.
#include <iostream>
#include <vector>
#define INT_MAX 10000000
using namespace std;
void DijkstrasTest();
int main()
{
DijkstrasTest();
return 0;
}
class Node;
class Edge;
void Dijkstras();
vector<Node*>* AdjacentRemainingNodes(Node* node);
Node* ExtractSmallest(vector<Node*>& nodes);
int Distance(Node* node1, Node* node2);
bool Contains(vector<Node*>& nodes, Node* node);
void PrintShortestRouteTo(Node* destination);
vector<Node*> nodes;
vector<Edge*> edges;
class Node
{
public:
Node(char id)
: id(id), previous(NULL), distanceFromStart(INT_MAX)
{
nodes.push_back(this);
}
public:
char id;
Node* previous;
int distanceFromStart;
};
class Edge
{
public:
Edge(Node* node1, Node* node2, int distance)
: node1(node1), node2(node2), distance(distance)
{
edges.push_back(this);
}
bool Connects(Node* node1, Node* node2)
{
return (
(node1 == this->node1 &&
node2 == this->node2) ||
(node1 == this->node2 &&
node2 == this->node1));
}
public:
Node* node1;
Node* node2;
int distance;
};
///////////////////
void DijkstrasTest()
{
Node* a = new Node('a');
Node* b = new Node('b');
Node* c = new Node('c');
Node* d = new Node('d');
Node* e = new Node('e');
Node* f = new Node('f');
Node* g = new Node('g');
Edge* e1 = new Edge(a, c, 1);
Edge* e2 = new Edge(a, d, 2);
Edge* e3 = new Edge(b, c, 2);
Edge* e4 = new Edge(c, d, 1);
Edge* e5 = new Edge(b, f, 3);
Edge* e6 = new Edge(c, e, 3);
Edge* e7 = new Edge(e, f, 2);
Edge* e8 = new Edge(d, g, 1);
Edge* e9 = new Edge(g, f, 1);
a->distanceFromStart = 0; // set start node
Dijkstras();
PrintShortestRouteTo(f);
}
///////////////////
void Dijkstras()
{
while (nodes.size() > 0)
{
Node* smallest = ExtractSmallest(nodes);
vector<Node*>* adjacentNodes =
AdjacentRemainingNodes(smallest);
const int size = adjacentNodes->size();
for (int i=0; i<size; ++i)
{
Node* adjacent = adjacentNodes->at(i);
int distance = Distance(smallest, adjacent) +
smallest->distanceFromStart;
if (distance < adjacent->distanceFromStart)
{
adjacent->distanceFromStart = distance;
adjacent->previous = smallest;
}
}
delete adjacentNodes;
}
}
// Find the node with the smallest distance,
// remove it, and return it.
Node* ExtractSmallest(vector<Node*>& nodes)
{
int size = nodes.size();
if (size == 0) return NULL;
int smallestPosition = 0;
Node* smallest = nodes.at(0);
for (int i=1; i<size; ++i)
{
Node* current = nodes.at(i);
if (current->distanceFromStart <
smallest->distanceFromStart)
{
smallest = current;
smallestPosition = i;
}
}
nodes.erase(nodes.begin() + smallestPosition);
return smallest;
}
// Return all nodes adjacent to 'node' which are still
// in the 'nodes' collection.
vector<Node*>* AdjacentRemainingNodes(Node* node)
{
vector<Node*>* adjacentNodes = new vector<Node*>();
const int size = edges.size();
for(int i=0; i<size; ++i)
{
Edge* edge = edges.at(i);
Node* adjacent = NULL;
if (edge->node1 == node)
{
adjacent = edge->node2;
}
else if (edge->node2 == node)
{
adjacent = edge->node1;
}
if (adjacent && Contains(nodes, adjacent))
{
adjacentNodes->push_back(adjacent);
}
}
return adjacentNodes;
}
// Return distance between two connected nodes
int Distance(Node* node1, Node* node2)
{
const int size = edges.size();
for(int i=0; i<size; ++i)
{
Edge* edge = edges.at(i);
if (edge->Connects(node1, node2))
{
return edge->distance;
}
}
return -1; // should never happen
}
// Does the 'nodes' vector contain 'node'
bool Contains(vector<Node*>& nodes, Node* node)
{
const int size = nodes.size();
for(int i=0; i<size; ++i)
{
if (node == nodes.at(i))
{
return true;
}
}
return false;
}
///////////////////
void PrintShortestRouteTo(Node* destination)
{
Node* previous = destination;
cout << "Distance from start: "
<< destination->distanceFromStart << endl;
while (previous)
{
cout << previous->id << " ";
previous = previous->previous;
}
cout << endl;
}
// these two not needed
vector<Edge*>* AdjacentEdges(vector<Edge*>& Edges, Node* node);
void RemoveEdge(vector<Edge*>& Edges, Edge* edge);
vector<Edge*>* AdjacentEdges(vector<Edge*>& edges, Node* node)
{
vector<Edge*>* adjacentEdges = new vector<Edge*>();
const int size = edges.size();
for(int i=0; i<size; ++i)
{
Edge* edge = edges.at(i);
if (edge->node1 == node)
{
cout << "adjacent: " << edge->node2->id << endl;
adjacentEdges->push_back(edge);
}
else if (edge->node2 == node)
{
cout << "adjacent: " << edge->node1->id << endl;
adjacentEdges->push_back(edge);
}
}
return adjacentEdges;
}
void RemoveEdge(vector<Edge*>& edges, Edge* edge)
{
vector<Edge*>::iterator it;
for (it=edges.begin(); it<edges.end(); ++it)
{
if (*it == edge)
{
edges.erase(it);
return;
}
}
}
