Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <fstream>
- using namespace std;
- double **A;
- int n;
- int *predecesor;
- const double MaxInf = 1.e20;
- void Citire_Date(const char numeFisier[]) {
- int i,j;
- double c;
- ifstream fin(numeFisier);
- fin >> n;
- A = new double*[n];
- if(A==0) {
- cout<<"alocare esuata";
- exit(1);
- }
- for(i=0;i<n;i++) {
- A[i]=new(nothrow) double[n];
- if(A[i]==0){
- cout<<"alocare esuata";
- exit(1);
- }
- for(j=0;j<n;j++)
- if(i==j)
- A[i][j]=0.0;
- else
- A[i][j] = MaxInf;
- }
- while(fin>>i>>j>>c)
- A[i][j]=c;
- fin.close();
- }
- void afisare(int i) {
- if (predecesor[i] != -1)
- afisare(predecesor[i]);
- cout << i << " ";
- }
- int main() {
- Citire_Date("in.txt");
- predecesor = new int [n];
- int *selectat = new int[n];
- double *dmin = new double[n], min;
- int v, w = -1;
- for (int i = 0; i < n; i++) {
- selectat[i] = 0;
- dmin[i] = 0.0;
- predecesor[i] = -1;
- }
- cout << "v: ";
- cin >> v;
- selectat[v] = 1;
- for (int i = 0; i < n; i++) {
- dmin[i] = A[v][i];
- if (i != v)
- if (dmin[i] < MaxInf) predecesor[i] = v;
- }
- for (int i = 1; i <= n - 1; i++){
- min = MaxInf;
- for (int j = 0; j < n; j++)
- if (selectat[j] == 0)
- if (dmin[j] < min) {
- min = dmin[j];
- w = j;
- }
- if (w != -1) {
- selectat[w] = 1;
- for (int j = 0; j < n; j++)
- if (selectat[j] == 0)
- if (dmin[j] > dmin[w] + A[w][j]) {
- dmin[j] = dmin[w] + A[w][j];
- predecesor[j] = w;
- }
- }
- }
- for (int i = 0; i < n; i++)
- if (i != v)
- if (predecesor[i] != -1) {
- cout << "Costul drumului de la " << v << " la " << i
- << " este " << dmin[i] << endl;
- afisare(i);
- cout << endl;
- } else
- cout << "Nu exista drum de la " << v << " la " << i << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement