Algorytm Dijkstry
![](http://178.128.105.246/host-http-upload.wikimedia.org/wikipedia/commons/5/57/Dijkstra_Animation.gif)
Algorytm uod Dijkstry - algorytm zbajstlowany bez ńiderlandzkego informatikera Edsgera Dijkstre do znojdowańo nojkrůtszyj drogi we grafje ze jednego knota do reszty knotůw. Algorytm ńy dźało kej ftoroś kanta mo ujymny wert dugości. We praktyce do śe uůnygo sztosować ntp. do sznupańo nojkrůtszyj drogi do danych punktůw uod karty. Wuůnczas zdefińować trza krziżowańa drogůw kej knoty, a same drogi i jich dugośći kej kanty co utworzi graf.
Fůngowańe
[edytuj | edytuj zdrzōdło]Nojsamprzůd dany momy graf a wybrany jedyn jigo knot, ze kerygo bydymy sztartować.
- Naszkryflej lista wszyjskich knotůw i naszkryflej przi kożdym knoće, aże droga do ńygo je ńyskończyńe dugo. Ino przi szartowym knoće wpisz dugość růwno 0.
- 'Půdź' do sztartowego knota.
- Zobocz kaj prowadzům bezpostrzedńo kanty ze knota przi kerym żeś je. Skreślij kanty kere prowadzům do skreślůnych knotůw[1]. Lo kożdyj kanty przi twojim knoće, kero ńy je skreślůno zrůb to samo:
- Zobocz na liśće, kery ńyskleślůny knot mo nojkrůtszo droga dojśćo. Půdź sam i skreślij knot ze kerygo żeś wyloz[5]. Wykonej punkt 3 algorytmu.
Algorytm śe kůńczy kej uostańe ino jedyn ńyskrelůny knot. Naszkryflano lista dowo nojkrůtsze drogi dojśćo ze knota sztartowygo do reszty knotůw we grafje.
Kod algorytmu
[edytuj | edytuj zdrzōdło]Podany sam bajszpil we C++ realizuje Algorytm Dijkstry lo grafu kaj kanty to drogi, kere do śe przelyź we uobu kerunkach.
Kod we C++ |
#include <iostream>
#include <vector>
#include <list>
#include <set>
#include <map>
using namespace std;
const double maximumWeight = numeric_limits<double>::infinity();
struct neighbor
{
int targetIndex;
string name;
double weight;
neighbor(int _target, string _name, double _weight) : targetIndex(_target), name(_name), weight(_weight) { }
};
void ComputeShortestPathsByDijkstra(int startIndex, const vector<vector<neighbor>>& adjacencyList, vector<double>& minimumDistances, vector<int>& previousVertices, map<int, string>& vertexNames)
{
int numberOfVertices = adjacencyList.size();
minimumDistances.clear();
minimumDistances.resize(numberOfVertices, maximumWeight);
minimumDistances[startIndex] = 0;
previousVertices.clear();
previousVertices.resize(numberOfVertices, -1);
set<pair<double, int>> vertexQueue;
vertexQueue.insert(make_pair(minimumDistances[startIndex], startIndex));
vertexNames.insert(make_pair(startIndex, vertexNames[startIndex]));
while (!vertexQueue.empty())
{
double distance = vertexQueue.begin()->first;
int index = vertexQueue.begin()->second;
vertexQueue.erase(vertexQueue.begin());
const vector<neighbor>& neighbors = adjacencyList[index];
// Diese for-Schleife durchläuft alle Nachbarn des Knoten mit index
for (vector<neighbor>::const_iterator neighborIterator = neighbors.begin(); neighborIterator != neighbors.end(); neighborIterator++)
{
int targetIndex = neighborIterator->targetIndex;
string name = neighborIterator->name;
double weight = neighborIterator->weight;
double currentDistance = distance + weight;
if (currentDistance < minimumDistances[targetIndex])
{
vertexQueue.erase(make_pair(minimumDistances[targetIndex], targetIndex));
vertexNames.erase(targetIndex);
minimumDistances[targetIndex] = currentDistance;
previousVertices[targetIndex] = index;
vertexQueue.insert(make_pair(minimumDistances[targetIndex], targetIndex));
vertexNames.insert(make_pair(targetIndex, name));
}
}
}
}
list<string> GetShortestPathTo(int index, vector<int>& previousVertices, map<int, string>& vertexNames)
{
list<string> path;
for (; index != -1; index = previousVertices[index])
{
path.push_front(vertexNames[index]);
}
return path;
}
int main()
{
vector<vector<neighbor>> adjacencyList(6);
adjacencyList[0].push_back(neighbor(1, "Knot 1", 7));
adjacencyList[0].push_back(neighbor(2, "Knot 2", 9));
adjacencyList[0].push_back(neighbor(5, "Knot 5", 14));
adjacencyList[1].push_back(neighbor(0, "Knot 0", 7));
adjacencyList[1].push_back(neighbor(2, "Knot 2", 10));
adjacencyList[1].push_back(neighbor(3, "Knot 3", 15));
adjacencyList[2].push_back(neighbor(0, "Knot 0", 9));
adjacencyList[2].push_back(neighbor(1, "Knot 1", 10));
adjacencyList[2].push_back(neighbor(3, "Knot 3", 11));
adjacencyList[2].push_back(neighbor(5, "Knot 5", 2));
adjacencyList[3].push_back(neighbor(1, "Knot 1", 15));
adjacencyList[3].push_back(neighbor(2, "Knot 2", 11));
adjacencyList[3].push_back(neighbor(4, "Knot 4", 6));
adjacencyList[4].push_back(neighbor(3, "Knot 3", 6));
adjacencyList[4].push_back(neighbor(5, "Knot 5", 9));
adjacencyList[5].push_back(neighbor(0, "Knot 0", 14));
adjacencyList[5].push_back(neighbor(2, "Knot 2", 2));
adjacencyList[5].push_back(neighbor(4, "Knot 4", 9));
vector<double> minimumDistances;
vector<int> previousVertices;
map<int, string> vertexNames;
ComputeShortestPathsByDijkstra(0, adjacencyList, minimumDistances, previousVertices, vertexNames);
cout << "Dugość uod knota 0 do knota 4: " << minimumDistances[4] << endl;
list<string> path = GetShortestPathTo(4, previousVertices, vertexNames);
cout << "Nojkrůtszo droga:";
copy(path.begin(), path.end(), ostream_iterator<string>(cout, " "));
cout << endl;
}
|