Der Algorithmus von Dijkstra ermöglicht es uns, den kürzesten Weg zwischen zwei beliebigen Scheitelpunkten in einem Diagramm zu finden.
Es unterscheidet sich von einem minimalen Spannbaum darin, dass der kürzeste Abstand zwischen zwei Scheitelpunkten möglicherweise nicht alle Scheitelpunkte im Diagramm enthält.
Wie der Algorithmus von Dijkstra funktioniert
Der Algorithmus von Dijkstra funktioniert auf der Grundlage, dass jeder Teilweg B -> D des kürzesten Weges A -> D zwischen den Scheitelpunkten A und D auch der kürzeste Weg zwischen den Scheitelpunkten B und D ist.
Dijkstra nutzte diese Eigenschaft in umgekehrter Richtung, d.h. Wir schätzen den Abstand jedes Scheitelpunkts vom ursprünglichen Scheitelpunkt erneut ab. Wir besuchen dann jeden Knoten und seine Nachbarn, um den kürzesten Teilpfad zu diesen Nachbarn zu finden.
Der Algorithmus verwendet einen "gierigen" Ansatz in dem Sinne, dass wir die nächstbeste Lösung finden, in der Hoffnung, dass das Endergebnis die beste Lösung für das gesamte Problem ist.
Ein Beispiel für den Algorithmus von Dijkstra
Es ist einfacher, mit einem Beispiel zu beginnen und dann über den Algorithmus nachzudenken.
Dijkstra-Algorithmus. Pseudocode.
Wir müssen die Pfadentfernung jedes Scheitelpunkts speichern. Wir können es in einem Array der Größe v speichern, wobei v die Anzahl der Scheitelpunkte ist.
Wir möchten auch den kürzesten Weg erhalten und nicht nur seine Länge kennen. Dazu ordnen wir jeden Scheitelpunkt der letzten aktualisierten Pfadlänge zu.
Sobald der Algorithmus beendet ist, können wir vom Zielknoten zum Quellknoten zurückkehren, um den Pfad zu finden.
Eine Warteschlange mit minimaler Priorität kann verwendet werden, um effizient den Scheitelpunkt mit dem kleinsten Pfadabstand zu erhalten.
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[]
Code für den Algorithmus von Dijkstra
Eine Implementierung des Dijkstra-Algorithmus in C++ ist unten angegeben. Die Komplexität des Codes kann verbessert werden, aber Abstraktionen sind gut, um Code mit einem Algorithmus in Beziehung zu setzen.
#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;
}
}
}
