Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define INF 1000000
- #include <fstream>
- using namespace std;
- ifstream fin("dijkstra.in");
- ofstream fout("dijkstra.out");
- int nr_noduri, nod_start, Graf[105][105];
- int D[105], P[105];
- bool viz[105];
- void citire()
- {
- int nod1, nod2, cost;
- fin>>nr_noduri>>nod_start;
- for(int i=1; i<=nr_noduri; i++)
- for(int j=1; j<i; j++)
- Graf[i][j]=Graf[j][i]=INF;
- while(fin>>nod1>>nod2>>cost)
- Graf[nod1][nod2]=cost;
- }
- void Init()
- {
- for(int j=1; j<=nr_noduri; j++)
- {
- D[j]=Graf[nod_start][j];
- P[j]=nod_start;
- }
- P[nod_start]=0;
- viz[nod_start]=1;
- }
- void Dijkstra()
- {
- int minn, poz_min;
- for(int k=1; k<=nr_noduri; k++)
- {
- minn=INF;
- for(int i=1; i<=nr_noduri; i++)
- if(minn>D[i] && viz[i]==0)
- minn=D[i], poz_min=i;
- viz[poz_min]=1;
- for(int i=1; i<=nr_noduri; i++)
- if(!viz[i] && D[i]>D[poz_min]+Graf[poz_min][i])
- {
- D[i]=D[poz_min]+Graf[poz_min][i];
- P[i]=poz_min;
- }
- }
- }
- void afisare(int x)
- {
- if(x != nod_start)
- afisare(P[x]);
- fout<<x<<" ";
- }
- int main()
- {
- citire();
- Init();
- Dijkstra();
- for(int i=1; i<=nr_noduri; i++)
- {
- if(D[i]==INF)
- fout<<-1<<" ";
- else
- fout<<D[i]<<" ";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement