Algorytm Dijkstry

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.

Dźołańy algorytmu uod Dijsktry na bajszpilu. Anfang je we knoće a, na modro naszkryflane sům aktuelńy nojkrůtsze wysznupane dugośći dojśćo do knota. Wyńikym je, aże ze knota 1 do 5 nojkrůtszo droga mo dugość 20.

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^[1]. 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^[2]. Zobejrz czy na liśće knot do kerego ta kanta idźe je uoznaczůny majsům nůmerům^[3]. Eli ja to ńy růb nic, eli ńy to sprowjej aktuelno dugość drogi na ta, ftoro sam wyszła^[4].
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

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

Przipisy

↑ Na poczůntku takich ńy bydźe.
↑ Ntp. we pryjszym kroku be to 0 + wert kanty.
↑ Nojpjyrw be to ńyskończůność, czyli ńy.
↑ Nojpjyrw be trza půmjyńić ńyskończůność na wert tyj kanty.
↑ Za pjyrszym razym be trza śkreślić sztartowy knot.

[1] Na poczůntku takich ńy bydźe.

[2] Ntp. we pryjszym kroku be to 0 + wert kanty.

[3] Nojpjyrw be to ńyskończůność, czyli ńy.

[4] Nojpjyrw be trza půmjyńić ńyskończůność na wert tyj kanty.

[5] Za pjyrszym razym be trza śkreślić sztartowy knot.

[1]

[2]

[3]

[4]

[5]