Nombres y apellidos: Alex Michael Quintos Pinedo
Cdigo: 1325220324
#include "dijkstra.h"
#include <iostream>
#include <iomanip>
struct DeQueuer
{
VertexInfo *r;
int n;
DeQueuer(): r(0),n(-1) {}
DeQueuer(VertexInfo *a, int b): r(a), n(b) {}
};
// Constructor makes a VertexInfo object with an "infinite"
// distance estimate, shortest path unknown, and no previous vertex
// on a shortest path from the start.
VertexInfo::VertexInfo(): distance(INF), known(false), previous(-1) {}
// Swap
static void swap(int& a, int& b)
{
int temp = a;
a = b;
b = temp;
}
//Dequeue
DeQueuer * dequeue(VertexList &v)
{
int min=0;
for(unsigned i=0; i<v.size(); i++)
if((v[min].distance > v[i].distance) && v[i].known==false)
min=i;
else if( v[i].known==false && v[min].known==true)
min=i;
DeQueuer *r;
if(v[min].known!=true)
{
v[min].known=true;
r=new DeQueuer(&v[min],min);
}
else
{
r=new DeQueuer(&v[min],-1);
}
return r;
}
// Computes the shortest path from the given start vertex
// to all other vertices in the graph represented by the
// given adjacency matrix.
VertexList dijkstra(AdjacencyMatrix m, int start)
{
VertexList V(m.size());
for(unsigned i=0; i<V.size(); i++)
V[i].distance=INF;
V[start].distance=0;
while(1)
{
DeQueuer *v=new DeQueuer;
v=dequeue(V);
if(v->n==-1) break;
if(v->r->distance == INF )
break;
for(unsigned i=0; i<m.size(); i++)
{
if(m[i][v->n]!=INF)
{
int d=v->r->distance + m[i][v->n];
if(d < V[i].distance)
{
V[i].distance=d; V[i].previous=v->n;
}
}
}
}
return V;
}
// Prints the path to this node from the start.
static void print_path(VertexList V, int pos)
{
if ( V[pos].previous != -1 )
{
print_path(V, V[pos].previous);
std::cout << " -> " << pos;
}
}
// Calls the dikstra function and reports the results.
void shortest_path(AdjacencyMatrix m, int start)
{
VertexList V = dijkstra(m, start);
std::cout << "Node | Dist. | Path" << std::endl;
std::cout << "-----+-------+--------" << std::endl;
for ( unsigned i = 0; i < V.size(); i++ )
{
std::cout << setw(4) << i << " | " << setw(5) << V[i].distance <<
" | ";
std::cout << start;
print_path(V, i);
std::cout << std::endl;
}
}
