lui_dijkstra.cpp

the algorithm of dijkstra

#include<iostream>
#include<fstream.h>
#include<conio.h>
using namespace std;

#define INFINIT 100

int d[10];
int t[10];
int s[10];

int n;
int m;
int a[10][10];

void citeste(int a[10][10],int &n,char file[]);
void afiseazaa(int a[10][10],int n);
void info();

void dijkstra(int x);

void main(){

        citeste(a,n,"D:\\matrice costuri.txt");
        cout<<"numarul varfurilor: "<<n<<endl;
        cout<<"matricea de adiacenta "<<endl;
        afiseazaa(a,n);
        dijkstra(1);
        info();

        getch();
}

void citeste (int a[10][10],int &n,char file[]){
        ifstream f(file);
        f>>n;
        for(int i=1;i<=n;i++)
                for(int j=1;j<=n;j++){
                        f>>a[i][j];
                }
}

void afiseazaa (int a[10][10],int n){
              cout<<"-------------------------------------"<<endl;
              for(int i=1;i<=n;i++){
                     for(int j=1;j<=n;j++){
                     cout.width(5);
                     cout<<a[i][j];
                      }
          cout<<endl;
        }
        cout<<"------------------------------------------"<<endl;
       }
void dijkstra(int x)
{
        int i,j,k,pas,min;
        for(i=1;i<=n;i++){
                s[i]=0;t[i]=-1;
                if(a[x][i]==INFINIT){
                        d[i]=INFINIT;
                        }else{
                                d[i]=a[x][i];
                                t[i]=x;
                        }
                }
                s[x]=1;
                t[x]=0;
                d[x]=0;

                for(pas=1;pas<=n-1;pas++){
                info();
                min=10000;
                k=-1;
                for(i=1;i<=n;i++)
                        if((s[i]==0)&&(d[i]<min)){
                                k=i;min=d[i];
                        }

                if(k==-1)return;

                s[k]=1;
                for(i=1;i<=n;i++)
                        if((s[i]==0)&&(d[k]+a[k][i]<d[i])){
                        d[i]=d[k]+a[k][i];
                        t[i]=k;
                        }
        }
}
void info(){
        cout<<"\n------------------------\n";
        cout<<"s:";for(int i=1;i<=n;i++) cout<<s[i]<<" ";
        cout<<endl;
        cout<<"t:"; for(int i=1;i<=n;i++) cout<<t[i]<<" ";
        cout<<endl;
        cout<<"d:"; for(int i=1;i<=n;i++) cout<<d[i]<<" ";
}