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.

 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ůwNa poczůntku takich ńy bydźe.. 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 kantyNtp. we pryjszym kroku be to 0 + wert kanty.. Zobejrz czy na liśće knot do kerego ta kanta idźe je uoznaczůny majsům nůmerůmNojpjyrw be to ńyskończůność, czyli ńy.. Eli ja to ńy růb nic, eli ńy to sprowjej aktuelno dugość drogi na ta, ftoro sam wyszłaNojpjyrw be trza půmjyńić ńyskończůność na wert tyj kanty..
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ś wylozZa pjyrszym razym be trza śkreślić sztartowy knot.. 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; 
}

Kategoria:Teoryjo grafůw
Kategoria:Algorytmy