Algortimo De Djisktra

#include <cstdio>

#include <queue>

#include <cstring>

using namespace std;

#define INF 999

#define MAXN 100

// los nodos en el grafo van de 1 a n

int C[MAXN][MAXN], // matriz de adyacencia, 0 si no estan conectados

// costo para ir de i a j si estan conectados

n, // numero de nodos

e; // numero de aristas

void iniGrafo()

{

for (int i=1; <=n; i++)

memset(&C[i][1], 0, n * sizeof(int));

}

void insertanodo(int a, int b, int c)

{

C[a][b] = C[b][a] = c;

}

int D[MAXN]; /* distancias minima desde s al nodo i */

int padre[MAXN]; /* ruta hacia el nodo i desde s */

int permanente[MAXN]; /* verdadero al tener la menor ruta al nodo i */

void dijkstra(int s)

{

priority_queue< pair<int,int> > pq;

pair <int,int> nodotmp;

int Vi, Vj;

// inicializacion

for (int i=1; i<=n; i++)

D[i] = INF,

padre[i] = -1,

permanente[i] = false;

// inicializacion del nodo inicial

D[s] = 0;

pq.push( pair <int,int> (D[s], s) );

// calculamos las distancias

while( !pq.empty() )

{

nodotmp = pq.top(); pq.pop();

Vi = nodotmp.second;

if ( !permanente[Vi] )

{

permanente[Vi] = true;

for (Vj = 1; Vj <= n; Vj++)

if ( !permanente[Vj] && C[Vi][Vj] > 0 && D[Vi] + C[Vi][Vj] < D[Vj] )

D[Vj] = D[Vi] + C[Vi][Vj],

padre[Vj] = Vi,

pq.push( pair <int,int> (-D[Vj], Vj) );

}

}

}

void imprimeGrafo(int n)

{

for (int i=1; i<=n; i++)

printf("%d(%d) ", i, D[i]);

printf("\n");

}

main()

{

int a, b, c;

// leemos el numero de nodos y aristas

scanf("%d%d", &n, &e);

// inicializamos el grafo

iniGrafo();

// leemos las aristas

for (int i=0; i<e; i++)

scanf("%d%d%d", &a, &b, &c),

insertanodo(a, b, c);

// usamos dijkstra para calcular la menor distancia

// desde el i-esimo nodo hacia los demas

for (int i=1; i<=n; i++)

dijkstra( i ),

printf("La menor distancia desde el nodo %d"

" hacia los otros nodos es:\n", i),

imprimeGrafo( n ),

printf("\n");

#include <map>

#include <queue>

using namespace std;

#define X first

#define Y second

template <class Node, class Edge=int> class Dijkstra {

public:

Dijkstra() {}

Dijkstra(const Node &n, const Edge &e=0) { push(n, e); }

bool empty() const { return q.empty(); }

void push(const Node &n, const Edge &e=0) {

Iter it = m.find(n);

if (it == m.end()) it = m.insert(make_pair(n, e)).X;

else if (it<>Y > e) it->Y = e;

else return;

q.push(make_pair(e, it));

}

const Node &pop() {

cur = q.top().Y;

do q.pop();

while (!q.empty() && q.top().Y->Y < q.top().X);

return cur->X;

}

const Edge &dist() const { return cur->Y; }

void link(const Node &n, const Edge &e=1) { push(n, cur->Y + e); }

private:

typedef typename map<Node, Edge>::iterator Iter;

typedef pair<Edge, Iter> Value;

struct Rank : public binary_function<Value, Value, bool> {

bool operator()(const Value& x, const Value& y) const {

return x.X > y.X;

}

};

map<Node, Edge> m;

priority_queue<Value, vector<Value>, Rank> q;

Iter cur;

};

// Ejemplo de uso (nodos y arcos están representados con enteros)

int shortestDistance(int nodes, int startNode, int endNode, int **dists) {

Dijkstra<int> dijkstra(startNode);

while (!dijkstra.empty()) {

int curNode = dijkstra.pop();

if (curNode == endNode)

return dijkstra.dist();

for (int i = 0; i < nodes; i++)

if (dists[curNode][i] >= 0) // "i" es un vecino de curNode

dijkstra.link(i, dists[curNode][i]); // añade arco con peso

}

return -1; // Ningún camino encontrado

}

procedure dijkstra (origen, destino : integer);

var

i, last, x : integer;

begin

// inicializacion

for i := 1 to vertices do

begin

d[i] := infinito;

marca[i] := false;

predecesores[i] := -1

end;

// --

d[origen] := 0; //inicializamos la distancia

marca[origen] := true; //marcas vertice origen como visitado

last := origen;

while marca[destino] = false do //mientras no se haya llegado al destino

begin

for i := 1 to vertices do //recorremos todos los vertices

begin;

if marca[i] = false then //si no ha sido marcado

if d[i] > d[last] + peso[last][i] then // si la d[i] mayor que el peso ponderado, fíjate que vector d[], inicialmente vale infinito

begin

d[i] := d[last] + peso[last][i]; //actualizamos vector distancias

predecesores[i] := last; //guardamos vertice visitado

end; // fin si

end; // fin for

x := menor_valor(); //vertice no marcado con menor distancia

marca[x] := true; //marcamos

last := x; //actualizamos el ultimo vertices

end; // fin mientras

end;

==========================================

function menor_valor : integer;

var

i, vericeMenor : integer;

menor : real;

begin

menor := infinito;

for i := 1 to vertices do

begin

if marca[i] = false then

...