# Cod sursa(job #149126)

Utilizator Data 5 martie 2008 12:47:57 Algoritmul lui Dijkstra 0 cpp done Arhiva educationala 1.24 kb
``````#include<iostream.h>
#include<conio.h>
#include<fstream.h>
long c[120][120],n,s[120],ant[120],d[120],i,j,k,pas,min,i0,m;
const infinit=90000;
void citire()
{
int i,j,k;
ifstream f("dijkstra.in");
f>>n>>m;

for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
if(i==j)
c[i][j]=0;
else
c[i][j]=infinit;
while(f>>i>>j>>k)

c[i][j]=k;
}

/*void drum(int i)
{
if(ant[i]!=0)
{
drum(ant[i]);
cout<<i<<" ";
}
else
cout<<i<<" ";
}
*/
int  main()
{

citire();
ofstream g("dijkstra.out");

i0=1;
for(i=1;i<=n;i++)
{
s[i]=0;
d[i]=c[i0][i];
if(d[i]<infinit)
ant[i]=i0;
else
ant[i]=0;
}
s[i0]=1;
ant[i0]=0;
for(pas=1;pas<n;pas++)
{
min=infinit;
for(i=1;i<=n;i++)
if(!s[i]&&d[i]<min)
{
min=d[i];
k=i;
}
s[k]=1;
for(i=1;i<=n;i++)
if(!s[i]&&d[i]>d[k]+c[k][i])
{
d[i]=d[k]+c[k][i];
ant[i]=k;
}
}
for(i=1;i<=n;i++)
{
// cout<<"drumul minim de la "<<i0<<"  la  "<<i<<" este "<<d[i]<<" : ";
// cout<<" trece prin ";
if(d[i]!=0)
// cout<<d[i]<<" ";
g<<d[i]<<" ";
// drum(i);
//cout<<endl;
}
// getch();
return 0;
}

``````