Алгоритм Дейкстры

[lolik228]

#include <iostream>
#include <string.h>
#include <fstream>

using namespace std;

int main(){

    ifstream fin("dijkstra.in");

    int N, S, F, i, j, count;
    int dist[100];
    int x[100];
    int PredVertex[100];
    int VES[100][100];
    int INF = 10000000;

    fin >> N >> S;

    for(i = 0; i < N; i++){
        for(j = 0; j < N; j++){
            fin >> VES [i][j];
        }
    }

    S = S - 1;

    cout << "  S      |    W    |    D(W)     |" << endl;

    for(count = 0; count < N; count++){
        F = count;
        if(F == S) continue;
        else{

    for(i = 0; i < N; i++){
        x[i] = 0;
        dist[i] = INF;
    }
    PredVertex[S] = 0;
    dist[S] = 0;
    x[S] = 1;
    int v = S;

    while(1){
        for(i = 0; i < N; i++){
            if(VES[v][i] == -1) continue;
            if(x[i] == 0 && dist[i] > dist[v] + VES[v][i]){
                dist[i] = dist[v] + VES[v][i];
                PredVertex[i] = v;
            }
        }
        int w = INF;
        v = -1;

        for(i = 0; i < N; i++){
            if(x[i] == 0 && dist[i] < w){
                v = i;
                w = dist[i];
            }
        }

      if(v == -1) break;

      if(v == F)
      {
       i = F;
      while(i!=S)
         {
            cout <<" "<<i+1;
            i = PredVertex[i];
         }
         cout<<" "<<S+1 <<"        " << F + 1 << "         " << dist[F] << endl;
       break;
      }

      x[v]=1;
    }}}
}