# Cod sursa(job #160403)

Utilizator Data 15 martie 2008 13:27:39 Algoritmul lui Dijkstra 0 cpp done Arhiva educationala 1.41 kb
``````#include <fstream>
using namespace std;
#define MAX 100
#define INF 32000

int n, m;
int d[MAX], s[MAX];
int a[MAX][MAX];
int t[MAX];

void Dijkstra(int sursa);

ifstream fin ("dijkstra.in");
ofstream fout ("dijkstra.out");

int main()
{
fin >> n >> m >> s;
int x, y, c;
for ( int i = 1; i <= n; i++ )
{
c[i][i] = 0;
for ( int j = i + 1; j <= n; j++ )
{
c[i][j] = INF;
c[j][i] = INF;
}
}
for ( int i = 0; i < m; i++ )
{
fin >> x >> y >> c;
a[x][y] = c;
a[y][x] = c;
}

Dijkstra(s);

for ( int i = 1; i <= n; i++ )
{
fout << d[i] << " ";
}

fin.close();
fout.close();

return 0;
}

void Dijkstra(int sursa)
{
d[sursa] = 0;
s[sursa] = 1;
t[sursa] = 0;

int min = INF;
for ( int p = 1; p < n; p++ )
{
min = INF;
int k = 0;
for ( int i = 1; i <= n; i++ )
{
if ( !s[i] && d[i] < min )
{
min = d[i];
k = i;
}
}
s[k] = 1;
for ( int i = 1; i <= n; i++ )
{
if ( !s[i] && d[i] > d[k] + c[k][i] )
{
d[i] = d[k] + c[k][i];
t[i] = k;
}
}
}
}
``````