[C++] Dijkstra Algorithm

[minghags]

Hello!

I want to ask you guys if anyone can help me correct my current program to read graph from a file instead of adding manual matrix in program.

Example graph:

graph.txt

8
1 2 3
1 3 6
1 8 1
2 3 2
2 8 2
3 4 1
4 5 6
4 6 3
4 7 4
5 6 3
6 7 2
7 8 10

code:

#include <iostream>
#include <vector>
using namespace std;

const double inf = 1000.0; 
const int nil = -1; 

void meni() {
    cout<<    "1 Vnos podatkov - rocni" << endl <<
    "2 Zagon algoritma" << endl <<
    "3 Izpis najkrajse poti" << endl <<
    "4 Konec" << endl << endl <<
    "Vasa izbira:" << endl;
}

void vnosPodatkov(double*& matrika, int& velikost) {
    cout << "Vnesi velikost matrike" << endl;
    cin >> velikost;
    int v2 = velikost*velikost;
    matrika = new double[v2];
    cout << "Vnesi elemente matrike" << endl;
    for(int i=0; i<v2; i++) {
        cin >> matrika[i];
    }
}

void dijkstrovAlgoritem(double*& matrika, int velikost, int s, double*& dolzina, int*& predhodnik) {
    vector<int> Q(velikost); 
    dolzina = new double[velikost];
    predhodnik = new int[velikost];

    for(int i=0; i<velikost; i++) {
        dolzina[i] = inf;
        predhodnik[i] = nil;
    }
    dolzina[s] = 0;

    for(int i=0; i<velikost; i++) {
        Q.push_back(i);
    }

    while(!Q.empty()) {
        int minElement = 0;
        double minVrednost = dolzina[Q[0]];
        int velikostQ = Q.size();
        for(int i=1; i<velikostQ; i++) {
            if(dolzina[Q[i]] < minVrednost) {
                minElement = i;
                minVrednost = dolzina[Q[i]];
            }
        }

        int u = Q[minElement]; 
        Q.erase(Q.begin()+minElement);

        int prvi = u*velikost;
        int zadnji = prvi+velikost;
        for(int i=prvi; i<zadnji; i++) {
            double razdalja = matrika[i];
            if(razdalja > 0 && razdalja < inf) {
                int v = i%velikost;
                if(dolzina[v] > dolzina[u]+matrika[i]) {
                    dolzina[v] = dolzina[u]+matrika[i];
                    predhodnik[v] = u;
                }
            }
        }
    }
}

void izpisPoti(double*& dolzina, int*& predhodnik, int s, int v) {
    if(s == v) {
        cout << s << ": dolžina: " << dolzina[s] << endl;
    } else if(predhodnik[v] == nil) {
        cout << "med " << s << " in " << v << " ni poti" << endl;
    } else {
        izpisPoti(dolzina, predhodnik, s, predhodnik[v]);
        cout << v << ": dolžina: " << dolzina[v] << endl;
    }
}

int main() {
    char izbira = 0x00;
    int velikost = 0;
    double* matrika;
    int s = -1;
    int v;
    double* dolzina; 
    int* predhodnik;

    while(true) {
        meni();
        cin >> izbira;

        if(izbira == '1') {
            vnosPodatkov(matrika, velikost);
        } else if(izbira == '2') {
            if(velikost == 0) {
                cout << "Vnesi podatke" << endl;
            } else {
                cout << "Vpisi zacetno vozlisce" << endl;
                cin >> s;
                if(s >= 0 && s < velikost) {
                    dijkstrovAlgoritem(matrika, velikost, s, dolzina, predhodnik);
                } else {
                    cout << "Ni vozlisca" << endl;
                }
            }
        } else if(izbira == '3') {
            if(s == -1) {
                cout << "Najprej zazeni algoritem" << endl;
            } else {
                cout << "Vpisi koncno vozlisce" << endl;
                cin >> v;
                if(v >= 0 && v < velikost) {
                    izpisPoti(dolzina, predhodnik, s, v);
                } else {
                    cout << "Ni vozlisca" << endl;
                }
            }
        } else if(izbira == '4') {
            return 0;
        } else {
            cout << "Napacna izbira" << endl;
            return 0;
        }
    }
}

Thank you very much in advance!

[ravenous]

You can read from a file in a similar was to the way that you read from user console input. You need to include <fstream>:

#include <fstream>
#include <iostream>
#include <vector>

int main()
{
    std::ifstream my_file( "testFile.txt", std::ios::in );
    if ( ! my_file.is_open() )
    {
        std::cerr << "Error!" << std::endl;
        return 1;
    }

    // Make a place to store the values
    std::vector< int > values;

    // Go through the file and put all the values in the vector
    while ( ! my_file.fail() ) {
        int value;
        my_file >> value;
        values.push_back( value );
    }

    std::cout << "Read values:" << std::endl;
    for ( std::vector< int >::const_iterator it = values.begin(); it != values.end(); ++it )
        std::cout << *it << std::endl;

    return 0;
}

You can also do this very nicely using istream_iterator:

#include <fstream>
#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>

int main()
{
    // Open the file an check that everything went OK
    std::ifstream my_file( "testFile.txt", std::ios::in );
    if ( ! my_file.is_open() )
    {
        std::cerr << "Error!" << std::endl;
        return 1;
    }

    // Make a vector to store the values in
    std::vector< int > values;

    // Read the values from the file
    std::copy( std::istream_iterator< int >( my_file ), std::istream_iterator< int >(), std::back_inserter( values ) );

    // Write the values out to the console
    std::cout << "Read values:" << std::endl;
    std::copy( values.begin(), values.end(), std::ostream_iterator< int >( std::cout, "\n" ) );
    return 0;
}

Hope that's some help :)

[minghags]

Ive done it like this, but have to return it so that algorithm can check them, but i don't have a clue how :S I didn't do anything with files before, if anyone can help thanks...

#include <iostream>
#include <vector>
#include <fstream>
#include <iostream>
using namespace std;

const double inf = 1000.0; 
const int nil = -1; 

void meni() {
    cout<<    "1 Vnos podatkov - rocni" << endl <<
    "2 Zagon algoritma" << endl <<
    "3 Izpis najkrajse poti" << endl <<
    "4 Konec" << endl << endl <<
    "Vasa izbira:" << endl;
}

void vnosPodatkov(double*& matrika, int& velikost) {

    std::ifstream my_file( "/Users/*****************/Desktop/graph.txt", std::ios::in );
    if ( ! my_file.is_open() )
    {
        std::cerr << "Error!" << std::endl;
        return 1;
    }
    // Make a place to store the values
    std::vector< int > values;
    // Go through the file and put all the values in the vector
    while ( ! my_file.fail() ) {
        int value;
        my_file >> value;
        values.push_back( value );
    }
    std::cout << "Read values:" << std::endl;
    for ( std::vector< int >::const_iterator it = values.begin(); it != values.end(); ++it )
        std::cout << *it << std::endl;
    return values;

}

void dijkstrovAlgoritem(double*& matrika, int velikost, int s, double*& dolzina, int*& predhodnik) {
    vector<int> Q(velikost); 
    dolzina = new double[velikost];
    predhodnik = new int[velikost];

    for(int i=0; i<velikost; i++) {
        dolzina[i] = inf;
        predhodnik[i] = nil;
    }
    dolzina[s] = 0;

    for(int i=0; i<velikost; i++) {
        Q.push_back(i);
    }

    while(!Q.empty()) {
        int minElement = 0;
        double minVrednost = dolzina[Q[0]];
        int velikostQ = Q.size();
        for(int i=1; i<velikostQ; i++) {
            if(dolzina[Q[i]] < minVrednost) {
                minElement = i;
                minVrednost = dolzina[Q[i]];
            }
        }

        int u = Q[minElement]; 
        Q.erase(Q.begin()+minElement);

        int prvi = u*velikost;
        int zadnji = prvi+velikost;
        for(int i=prvi; i<zadnji; i++) {
            double razdalja = matrika[i];
            if(razdalja > 0 && razdalja < inf) {
                int v = i%velikost;
                if(dolzina[v] > dolzina[u]+matrika[i]) {
                    dolzina[v] = dolzina[u]+matrika[i];
                    predhodnik[v] = u;
                }
            }
        }
    }
}

void izpisPoti(double*& dolzina, int*& predhodnik, int s, int v) {
    if(s == v) {
        cout << s << ": dolžina: " << dolzina[s] << endl;
    } else if(predhodnik[v] == nil) {
        cout << "med " << s << " in " << v << " ni poti" << endl;
    } else {
        izpisPoti(dolzina, predhodnik, s, predhodnik[v]);
        cout << v << ": dolžina: " << dolzina[v] << endl;
    }
}

int main() {
    char izbira = 0x00;
    int velikost = 0;
    double* matrika;
    int s = -1;
    int v;
    double* dolzina; 
    int* predhodnik;

    while(true) {
        meni();
        cin >> izbira;

        if(izbira == '1') {
            vnosPodatkov(matrika, velikost);
        } else if(izbira == '2') {
            if(velikost == 0) {
                cout << "Vnesi podatke" << endl;
            } else {
                cout << "Vpisi zacetno vozlisce" << endl;
                cin >> s;
                if(s >= 0 && s < velikost) {
                    dijkstrovAlgoritem(matrika, velikost, s, dolzina, predhodnik);
                } else {
                    cout << "Ni vozlisca" << endl;
                }
            }
        } else if(izbira == '3') {
            if(s == -1) {
                cout << "Najprej zazeni algoritem" << endl;
            } else {
                cout << "Vpisi koncno vozlisce" << endl;
                cin >> v;
                if(v >= 0 && v < velikost) {
                    izpisPoti(dolzina, predhodnik, s, v);
                } else {
                    cout << "Ni vozlisca" << endl;
                }
            }
        } else if(izbira == '4') {
            return 0;
        } else {
            cout << "Napacna izbira" << endl;
            return 0;
        }
    }
}