GRAFURI ORIENTATE

Fisierul graf.txt:

8

A B C D E F G H

0 9 1 3 999 999 9 999

999 0 999 999 999 999 999 999

999 999 0 999 2 5 999 999

999 999 999 0 999 999 5 999

999 4 999 999 0 1 999 999

999 999 999 999 999 0 1 999

999 999 999 999 999 999 0 999

999 999 999 1 999 4 2 0

#include <iostream>

#include <fstream>

#include <limits>

#define MAX 100

using namespace std;

int infinit = 999;

int numarNoduri;

int matriceAdiacenta[MAX][MAX];

char vector[MAX];

void citire()

{

ifstream f("graf.txt");

int i,j;

f>>numarNoduri;

for(i=1;i<=numarNoduri;i++)

f>>vector[i];

for(i=1;i<=numarNoduri;i++)

for(j=1;j<=numarNoduri;j++)

f>>matriceAdiacenta[i][j];

f.close();

}

void afisareMatrice()

{

int i,j;

for(i=1;i<=numarNoduri;i++)

{

for(j=1;j<=numarNoduri;j++)

cout<<matriceAdiacenta[i][j]<<" ";

cout<<endl;

}

}

void dijkstra(int nodInitial)

{

int i,j,min,k;

bool ok;

int vizitat[MAX]={0},distanta[MAX];

for (i=1;i<=numarNoduri; i++)

{

distanta[i]=matriceAdiacenta[nodInitial][i];

vizitat[i]=0;

}

vizitat[nodInitial]=1;

ok=true;

while(ok)

{

min=infinit;

for(i=1;i<=numarNoduri;i++)

if (!vizitat[i]&&min>distanta[i])

{

min=distanta[i];

k=i;

}

if (min!=infinit)

{

vizitat[k]=1;

for (i=1;i<=numarNoduri;i++)

if (!vizitat[i]&&distanta[i]>distanta[k]+matriceAdiacenta[k][i])

{

distanta[i]=distanta[k]+matriceAdiacenta[k][i];

}

}

else

ok=false;

}

cout<<"Distanta de la nodul initial la celalalte noduri este:";

for(i=1;i<=numarNoduri;i++)

cout<<endl<<distanta[i];

}

int main()

{

cout << "Hello world!" << endl;

citire();

int nodInitial;

cout<<"nodInitial=";cin>>nodInitial;

dijkstra(nodInitial);

return 0;

}