Algorytm Dijkstry

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

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. Lo kożdyj kanty przi twojim knoće, kero ńy je skreślůno zrůb to samo:
- Dodej dugość dojśćo do knota przi kerym żeś je ze dugośćům tyj kanty. Zobejrz czy na liśće knot do kerego ta kanta idźe je uoznaczůny majsům nůmerům. Eli ja to ńy růb nic, eli ńy to sprowjej aktuelno dugość drogi na ta, ftoro sam wyszła.
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. 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

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  #include  #include  #include  #include  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;  }

Przipisy

This article uses material from the Wikipedia Ślůnski article Algorytm Dijkstry, which is released under the Creative Commons Attribution-ShareAlike 3.0 license ("CC BY-SA 3.0"); additional terms may apply (view authors). Tekst udostympniany na licyncyji CC BY-SA 4.0, jeźli niy było podano inakszyj. Images, videos and audio are available under their respective licenses.
®Wikipedia is a registered trademark of the Wiki Foundation, Inc. Wiki Ślůnski (DUHOCTRUNGQUOC.VN) is an independent company and has no affiliation with Wiki Foundation.

Algorytm Dijkstry

Fůngowańe

Kod algorytmu

Przipisy

Tags:

🔥 Trending searches on Wiki Ślůnski: