Dijkstran algoritmia mytilev sov

// Copyright Petri Kuukkanen joulukuu 2006#include <iostream>#include <vector>#include <cmath>struct Crossing{  float x, y;  // risteyksen koordinaatit};struct Road{  unsigned int begin, end; // risteykset, joiden välillä tie kulkee  float length;            // tien pituus};std::vector<Crossing> crossings; // kaupungin kaikki risteyksetstd::vector<Road> roads;         // kaupungin kaikki tiet// Lisää tietorakenteeseen uusi risteys.void addCrossing(float x, float y){  Crossing c;  c.x = x;  c.y = y;  crossings.push_back(c);}// Lisää tietorakenteeseen uusi tie.void addRoad(unsigned int begin, unsigned int end, float length){  Road r;  r.begin  = begin;  r.end    = end;  r.length = length;  roads.push_back(r);}// Palauta kahden risteyksen välinen linnuntietä pitkin mitattu etäisyys.float crossingsDistance(unsigned int c1, unsigned int c2){  float x1, y1, x2, y2;  x1 = crossings[c1].x;  y1 = crossings[c1].y;  x2 = crossings[c2].x;  y2 = crossings[c2].y;  return sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));}// Etsi parhaat risteyksestä c alkavat reitit syvyyteen ensin -haulla.// Tämä on rekursiivinen (eli itseään kutsuva) funktio, jota kutsutaan// funktiosta findBestRoute.void findRoutes(unsigned int c, float l, int *R, float *L){  unsigned int e, r;  float f;  for(r = 0; r < roads.size(); r++)  {    if(roads[r].begin != c) continue;    e = roads[r].end;    f = l + roads[r].length;    if((R[e] == -1) || (L[e] > f))    {      R[e] = r;      L[e] = f;      findRoutes(e, f, R, L);    }  }}// Etsi paras reitti c:stä d:hen ja palauta reitin ensimmäisen tien numero.int findBestRoute(unsigned int c, unsigned int d){  if(c == d) return -1;  unsigned int i, j, k, N = crossings.size();  int   *R = new   int[N];  float *L = new float[N];  for(i = 0; i < N; i++) R[i] = -1;  findRoutes(c, 0, R, L);  j = R[d];  if(j != -1) while((k = roads[j].begin) != c) j = R[k];  delete[] R;  delete[] L;  return j;}int main(){  int i, j, k, N;  // Tee muutamia risteyksiä.  for(i = 0; i < 3; i++) for(j = 0; j < 3; j++) addCrossing(i, j);  N = crossings.size();  // Vector-luokan size-metodi palauttaa vektoriin                         // tallennettujen juttujen lukumäärän.  // Tee N kappaletta satunnaisia teitä.  for(i = 0; i < N; i++)  {    j = rand() % N;    k = rand() % N;    addRoad(j, k, crossingsDistance(j, k));  // menomatka j:stä k:hon    addRoad(k, j, crossingsDistance(k, j));  // paluumatka k:sta j:hin  }  // Näytä parhaat reitit.  for(i = 0; i < N; i++) for(j = 0; j < N; j++)  {    k = findBestRoute(i, j);    if(k != -1)    {      cout << i << " -> " << j;      cout << ": tie " << k << std::endl;    }  }  return 0;}