Pasar a ASP

[Pilly]

Buenas tardes foreros,

Quiero pedirles una ayudita con un algirtmo que encontré para una aplicación GIS que estoy desarrollando, no se en que lenguaje esta el algoritmo y me gustaria pasarlo a asp,no tengo mucha experiencia en este lenguaje por ello el abuso, se trata del algoritmo de Dijkstra para encontrar la ruta mas corta entre 2 puntos en un mapa.


Este es el algoritmo:

Código:

Begin
Initialise P={r}, T = V - {r}
Initialise d(s) = 0, pred(s) = 0
Let d(j) = C(n,j)
Let pred(j) = r

For all (s,j) € A
d(j) = ∞ for other nodes

While P ≠ V do
Chose minimun i € T
d(i) = min {d(j): j € T}

Update P and T
P = P{i}
T = T - {i}

Update temporaryLabels:
For all j € A(i)
Compute d(j) = min{d(j), d(i)+ C(i,j)}
Set pred(j) = I
End For
End Do
End For
End //End function

Muchas gracias de antemano
Pilly

[u_goldman]

No me hagas mucho caso pero a mi me parece que eso es Prolog
Quizas si te leas unos tutoriales, mas no puedo abundar.

Saludos

[luisvasquez]

Hola,

Yo también ando buscando el dichoso algoritmo en ASP...

En wikipedia encontré el código en C++

¿Alguien se atreve a pasarlo a ASP?

Código:

#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
}