• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Algorytm Dijkstry

Fiszki IT
Fiszki IT
0 głosów
77 wizyt
pytanie zadane 7 stycznia w C i C++ przez wodzu_37 Nowicjusz (160 p.)

W jaki sposób zmodyfikować poniższy kod aby prawidłowo czytał z wektora i obliczał drogę metodą D

#include <iostream>
#include <cstdlib>
#include <string>
#include <cstring>
#include <fstream>
#include <sstream>
#include <vector>
#include <algorithm>
#include <utility>

//#include "def.cpp"
//#include "funkcje.h"

using namespace std;
struct Node {
    string city;
    vector<pair<unsigned, unsigned>> connections;
};

int findOrAddCity(vector<Node>& g, const string& name)
{
    for (int i = 0; i < g.size(); i++)
        if (g[i].city == name) return i;

    g.push_back({ name, {} });
    return g.size() - 1;
}
int wczytaj_arg(int argc, char* argv[])
{

    int pozI = 0;
    int pozC = 0;
    string nPlikuI = "";
    string nPlikuC = "";
    string plik, centrala;
    if (argc == 5)
    {
        for (int i = 0; i < argc; i++) {
            if ((string(argv[i]) == "-i") and i < argc - 1) {
                pozI = i + 1;
                plik = argv[pozI];
            }
            if ((string(argv[i]) == "-c") and i < argc - 1) {
                pozC = i + 1;
                centrala = argv[pozC];
            }
        }
        cout << "\nNazwa pliku wejściowego : " << plik << endl;
        cout << "Nazwa Centrali: " << centrala << endl;

    }
    else
    {
        cout << "ZLE ARGUMENTY\n" << "PODAJ : \n\n" << "-i nazwa pliku wejsciowego \n -c nazwa centrali\n";
    }
    return pozI;
}
struct slistEl
{
    slistEl* next;
    int v, w;           // numer węzła docelowego i waga krawędzi
};

const int MAXINT = 2147483647;
int main(int argc, char* argv[])
{
    system("chcp 1250");
    system("cls");

    wczytaj_arg(argc, argv);
    string nazwa_pliku = argv[2];

    ifstream ifs(nazwa_pliku);
    vector<Node> graph;
    string m1, m2;
    unsigned dist;

    while (ifs >> m1 >> m2 >> dist) {
        int i1 = findOrAddCity(graph, m1);
        int i2 = findOrAddCity(graph, m2);
        graph[i1].connections.push_back(make_pair(i2, dist));
    }

    for (auto& i : graph) {
        cout << i.city << '\n';
        for (auto& c : i.connections)
            cout << '\t' << graph[c.first].city << " - " << c.second << '\n';
    }
    int i, j, m, n, v, u, w, x, y, sptr, * d, * p, * S;
    bool* QS;           // Zbiory Q i S
    slistEl** graf;     // Tablica list sÄ…siedztwa
    slistEl* pw, * rw;
    v = 0;
        n = 7;
        m = 7;
   // cin >> v >> n >> m; // Węzeł startowy, liczba wierzchołków i krawędzi

    // Tworzymy tablice dynamiczne

    d = new int[n];          // Tablica kosztów dojścia
    p = new int[n];          // Tablica poprzednikĂłw
    QS = new bool[n];        // Zbiory Q i S
    graf = new slistEl * [n]; // Tablica list sÄ…siedztwa
    S = new int[n];          // Stos
    sptr = 0;                   // WskaĹşnik stosu

    // Inicjujemy tablice dynamiczne

    for (i = 0; i < n; i++)
    {
        d[i] = MAXINT;
        p[i] = -1;
        QS[i] = false;
        graf[i] = NULL;
    }

    // Odczytujemy dane wejściowe

    for (i = 0; i < m; i++)
    {
        cin >> x >> y >> w;    // Odczytujemy krawędź z wagą
        pw = new slistEl;      // Tworzymy element listy sÄ…siedztwa
        pw->v = y;             // Wierzchołek docelowy krawędzi
        pw->w = w;             // Waga krawędzi
        pw->next = graf[x];
        graf[x] = pw;       // Element dołączamy do listy
    }

    cout << endl;

    d[v] = 0;             // Koszt dojścia v jest zerowy

    // Wyznaczamy ścieżki

    for (i = 0; i < n; i++)
    {
        // Szukamy wierzchołka w Q o najmniejszym koszcie d

        for (j = 0; QS[j]; j++);
        for (u = j++; j < n; j++)
            if (!QS[j] && (d[j] < d[u])) u = j;

        // Znaleziony wierzchołek przenosimy do S

        QS[u] = true;

        // Modyfikujemy odpowiednio wszystkich sÄ…siadĂłw u, ktĂłrzy sÄ… w Q

        for (pw = graf[u]; pw; pw = pw->next)
            if (!QS[pw->v] && (d[pw->v] > d[u] + pw->w))
            {
                d[pw->v] = d[u] + pw->w;
                p[pw->v] = u;
            }
    }

    // Gotowe, wyświetlamy wyniki

    for (i = 0; i < n; i++)
    {
        cout << i << ": ";

        // Ścieżkę przechodzimy od końca ku początkowi, 
        // Zapisując na stosie kolejne wierzchołki

        for (j = i; j > -1; j = p[j]) S[sptr++] = j;

        // Wyświetlamy ścieżkę, pobierając wierzchołki ze stosu

        while (sptr) cout << S[--sptr] << " ";

        // Na końcu ścieżki wypisujemy jej koszt

        cout << "$" << d[i] << endl;
    }

    // Usuwamy tablice dynamiczne

    delete[] d;
    delete[] p;
    delete[] QS;
    delete[] S;

    for (i = 0; i < n; i++)
    {
        pw = graf[i];
        while (pw)
        {
            rw = pw;
            pw = pw->next;
            delete rw;
        }
    }

    delete[] graf;
    system("pause");

    return 0;
}

ijkstry 

1 odpowiedź

0 głosów
odpowiedź 7 stycznia przez Wiciorny Mędrzec (166,950 p.)
Kto pisał w takim razie ten kod, zapytaj twórcę ? Skoro rozumiem, nie wiesz jak go modyfikować, to nie jest on twoim dziełem ?
komentarz 8 stycznia przez wodzu_37 Nowicjusz (160 p.)
https://eduinf.waw.pl/inf/alg/001_search/0138.php z tej strony jest skopiowany algorytm dijkstry . Więc nie jest to kod mojego autorstwa
1
komentarz 8 stycznia przez j23 Mędrzec (164,220 p.)
Może zamiast wklejać bezmyślnie kod, spróbuj zrozumieć algorytm i wtedy kombinuj.

Trochę to wygląda, jakbyś chciał, by ktoś odwalił za Ciebie robotę.
komentarz 8 stycznia przez wodzu_37 Nowicjusz (160 p.)
Próbowałem , jednak nie potrafię. Jestem w tym zielony
komentarz 8 stycznia przez Wiciorny Mędrzec (166,950 p.)
to zaimplementuj jakiś prostszy algorytm, zacznij od czegoś prostszego

Podobne pytania

0 głosów
0 odpowiedzi 61 wizyt
0 głosów
1 odpowiedź 218 wizyt
pytanie zadane 6 marca 2020 w C i C++ przez Ambitnystudent Nowicjusz (120 p.)
0 głosów
1 odpowiedź 106 wizyt
pytanie zadane 26 grudnia 2019 w C i C++ przez Dawid Penderewski Nowicjusz (120 p.)
Porady nie od parady
Zadając pytanie postaraj się o odpowiedni tytuł, kategorię oraz tagi.Tagi

84,762 zapytań

133,562 odpowiedzi

296,000 komentarzy

56,018 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto dwie polecane książki warte uwagi. Pełną listę znajdziesz tutaj.

...