Алгоритм Джонсона для графов

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "windows.h"
#include <string>
#include "Johnson.h"
using namespace std;
int main(int argc, char **argv){
 LARGE_INTEGER freq;
 LARGE_INTEGER sQP, fQP;
 QueryPerformanceFrequency(&freq);
 if (argc < 2){
 printf("\nUsage: program.exe <graph file> [-o]\n");
 return 1;
 }
 GraphMatrix *gr;
 int *up;
 int *dist;
 bool printOutput = false;
 ParseGraph(argv[1], &gr);
 if (argc == 3)
 if(string(argv[2]) == string("-o"))
 printOutput = true;
// pi - функция
 up = new int[gr->sizeV * gr->sizeV];
 // дистанция до вершины
 dist = new int[gr->sizeV * gr->sizeV];
 QueryPerformanceCounter(&sQP);
 Johnson(gr, up, dist);
 QueryPerformanceCounter(&fQP);
 printf("Johnson time: %f\n",
 (fQP.QuadPart-sQP.QuadPart)/ (double)freq.QuadPart );
 if(printOutput)
 {
 FILE *distFile=fopen("08_dist.dat", "wb");
 fwrite(dist, sizeof(int), gr->sizeV * gr->sizeV,
 distFile);
 fclose(distFile);
 printf("File (08_dist.dat) written.\n" );
 }
 delete[] gr->column;
 delete[] gr->pointerB;
 delete[] gr->value;
 delete gr;
 delete [] up;
 delete [] dist;
 return 0;
}
#ifndef DIJKSTRA_H
#define DIJKSTRA_H
#include "routine.h"
#include <cstdio>
#include <queue>
#include <algorithm>
//API
// void Dijkstra(graphMatrix *gr, int givenNode, int *up,
// int *dist);
// Алгоритм Дейкстры поиска кратчайших путей из источника
// во все вершины
//
//INPUT
// graphMatrix - взвешенный граф
// int - вершина источник
//
//OUTPUT
// int * - pi-функция
// int * - растояние до вершин
void Dijkstra(GraphMatrix *gr, int givenNode, int *up,
 int *dist);
#endif
struct Pair
{
 int dist;
 int node;
};
bool operator<(Pair p1, Pair p2)
{
 // более приоритетны меньшие элементы!
 return (p1.dist > p2.dist);
}
void Dijkstra(GraphMatrix *gr, int givenNode, int *up,
 int *dist)
{
 //все вершины бесконечно удалены
 for (int i=0; i < gr->sizeV; i++)
 dist[i] = INT_MAX;
 dist[givenNode] = 0;
 up[givenNode] = givenNode;
 priority_queue<Pair> pq;
 //помещаем стартовую вершину в приоритетную очередь
 Pair t = {0,givenNode};
 pq.push(t);
//поиск кратчайших путей
 while(!pq.empty())
 {
 // изымаем элемент из очереди
 Pair s = pq.top();
 pq.pop();
 // для изъятой вершины проверяем окрестность
 // на предмет уменьшения длин пути
 int okr_s = gr->pointerB[s.node];
 int okr_f = gr->pointerB[s.node + 1];
 for(int okr_i = okr_s; okr_i < okr_f; okr_i++)
 {
 int j = gr->column[okr_i];
 //релаксация
 if (dist[j] > (dist[s.node] + gr->value[okr_i]))
 {
 dist[j] = (dist[s.node] + gr->value[okr_i]);
 up[j] = s.node;
 //помещаем вершину в очередь, т.к. она может
 // уменьшить путь
 Pair p = {dist[j],j};
 pq.push(p);
 }
 }
  }
}
#ifndef JOHNSON_H
#define JOHNSON_H
#include "Dijkstra.h"
//API
// bool BellmanFord(graphMatrix *gr, int givenNode,
// int *dist);
// Алгоритм поиска кратчайшего пути во взвешенном графе из
// источника во все вершины
//
//INPUT
// graphMatrix - взвешенный граф
// int - вершина источник
//
//OUTPUT
// int * - растояние до вершин
bool BellmanFord(GraphMatrix *gr, int givenNode,
 int *dist);
//API
// void Johnson(graphMatrix *gr, int *up, int *dist);
// Алгоритм Джонсона поиска кратчайших путей между каждой
// парой вершин
//
//INPUT
// graphMatrix - взвешенный граф
//
//OUTPUT
// int * - pi-функция
// int * - растояние до вершин
void Johnson(GraphMatrix *gr, int *up, int *dist);
#endif
bool BellmanFord(GraphMatrix *gr, int givenNode,
 int *dist){
 // переменные прохода по окрестности вершины графа
  int okr_s, okr_f, okr_i;
 int i, j, k;
 // пока все вершины бесконечно удалены
 for (i=0; i < gr->sizeV; i++)
 dist[i] = INT_MAX;
 // растояние до начальной вершины равно 0
 dist[givenNode] = 0;
//поиск циклов и расстояний до вершин
 for (k=0; k < gr->sizeV - 1; k++)
 {
 for (i=0; i < gr->sizeV; i++)
 {
 //для изъятой вершины проверяем окрестность
 // на предмет уменьшения длин пути
 okr_s = gr->pointerB[i ];
 okr_f = gr->pointerB[i + 1];
 for(okr_i = okr_s; okr_i < okr_f; okr_i++)
 {
 j = gr->column[okr_i];
 //релаксация
 if (dist[j] - gr->value[okr_i] > dist[i])
 {
 dist[j] = dist[i] + gr->value[okr_i];
 }
 }
 }
 } 
 for (i = 0; i < gr->sizeV; i++)
 {
 okr_s = gr->pointerB[i ];
 okr_f = gr->pointerB[i + 1];
 for(okr_i = okr_s; okr_i < okr_f; okr_i++)
 {
 j = gr->column[okr_i];
 if (dist[j] > (dist[i] + gr->value[okr_i]))
 return false;
 }
 }
 return true;
}
void Johnson(GraphMatrix *gr, int *up, int *dist)
{
 int i, j, n;
 int okr_s, okr_f, okr_i;
 int *h;
 GraphMatrix gr_h;
 n = gr->sizeV;
 gr_h.sizeV = n + 1;
 gr_h.sizeE = gr->sizeE + n;
 gr_h.column = new int [gr->sizeE + n];
 gr_h.value = new int [gr->sizeE + n];
 gr_h.pointerB = new int [n + 2];
 h = new int [n + 1];
 for(i = 0; i < gr->sizeE; i++)
 {
 gr_h.column[i + n] = gr->column[i] + 1;
 gr_h.value [i + n] = gr->value [i];
 }
 gr_h.pointerB[0] = 0;
 for(i = 0; i < n; i++)
 {
 gr_h.pointerB[i + 1] = gr->pointerB[i] + n;
 gr_h.column[i] = i;
 gr_h.value [i] = 0;
 }
 gr_h.pointerB[i + 1] = gr->pointerB[i] + n;
 bool f = false;
 f = BellmanFord(&gr_h, 0, h);
 if (!f)
 {
    printf("exist negativ circle\n");
 return;
 }
  delete [] gr_h.column;
 delete [] gr_h.value;
 delete [] gr_h.pointerB;
for (i = 0; i < n; i++)
 {
 okr_s = gr->pointerB[i ];
 okr_f = gr->pointerB[i + 1];
 for(okr_i = okr_s; okr_i < okr_f; okr_i++)
 {
 j = gr->column[okr_i];
 gr->value[okr_i] += h[i + 1] - h[j + 1];
 }
 }
 for(i = 0; i < n; i++)
 Dijkstra(gr, i, up + n * i, dist + n * i);
 for (i = 0; i < n; i++)
 {
 okr_s = gr->pointerB[i ];
 okr_f = gr->pointerB[i + 1];
 for(okr_i = okr_s; okr_i < okr_f; okr_i++)
 {
 j = gr->column[okr_i];
 gr->value[okr_i] -= h[i + 1] - h[j + 1];
 }
 }
 for(i = 0; i < n; i++)
 for(j = 0; j < n; j++)
 dist[n * i + j] += h[j + 1] - h[i + 1];
 delete []h;
}