03/26 - Algoritmul lui Dijkstra

Algo.

#include <iostream>
#include <fstream>
using namespace std;
int a[20][20],d[20],viz[20],n,m,start;
void citire ()
{
    int i,x,y,c;
    ifstream fin ("graf.in");
    fin>>n>>m>>start;
    for (i=1;i<=m;i++){
        fin>>x>>y>>c;
        a[x][y]=c;
    }
}
void drum_minim ()
{
    int i,j,minim,nodminim;
    viz[start]=1;
    for (i=1;i<=n;i++){
        if (a[start][i]) d[i]=a[start][i];
        else d[i]=99999;
    }
    d[start]=0;
    for (i=1;i<=n;i++){
        minim=99999;
        for (j=1;j<=n;j++){
            if (!viz[j] && d[j]<minim){
                minim=d[j];
                nodminim=j;
            }
        }
        viz[nodminim]=1;
        for (j=1;j<=n;j++){
            if (a[nodminim][j] && d[j]>minim+a[nodminim][j])
                d[j]=minim+a[nodminim][j];
        }
    }
}
int main ()
{
    int i;
    citire ();
    drum_minim ();
    for (i=1;i<=n;i++){
        cout<<"Distanta minima dintre "<<start<<" si "<<i;
        cout<<" este "<<d[i]<<'\n';
       
    }
    return 0;
}

Fişier

8 13 2
1 2 1
1 3 10
2 3 6
2 4 1
4 3 3
4 6 5
4 5 1
5 3 1
3 8 10
6 5 2
6 7 3
7 8 1
5 8 25