[GML] Dijkstra's Algorithm (Beta)

// hapus(ii)
//where ii is index of vertex to be removed from unvisited vertex array q.
 ii=argument0
 for(iii=1;iii<=nq;iii+=1)
  if(q[iii]==ii)
  iv=iii;
 if(iv<=nq){
  if(iv<nq){
  for(iii=iv;iii<=nq-1;iii+=1){
    q[iii]=q[iii+1]
  }
  }
  nq-=1
 }

// ketemu(ii)
//where ii is index of vertex to be searched in vertex array q.
 ii=argument0
 ff=false
 for(iii=1;iii<=nq;iii+=1){
  if(q[iii]==ii)
  ff=true
 }
 return ff

// dijkstra(s)
//where s is index of source vertex.
//
//Required data
//vertices_dist[i]: Path distance from i to source s
//vertices_prev[i]: Previous path vertex from vertex i
//vertices_neighbors[i]: Number of neighbors of vertex i
//vertices_neighbor[i,j]: j-th neighbor vertex index of vertex i
//vertices_distb[i,j]: Distance between vertex i and j-th neighbor vertex of vertex i
 s=argument0
 for(i=1;i<=n;i+=1){
  vertices_dist[i]=99999
  vertices_prev[i]=0
  q[i]=i
  nq=n
 }
 vertices_dist[s]=0;
 while(nq>0){
 
  d=vertices_dist[q[1]]
  u=q[1]
  if(nq>1){
  for(ii=2;ii<=nq;i+=1){
  if(vertices_dist[q[ii]]<d){
    d=vertices_dist[q[ii]];
    u=q[ii];
  }
  }
  }

  if(vertices_dist[u]==99999) break;
  hapus(u);
  if(vertices_neighbors[u]>0){
  for(i=1;i<=vertices_neighbors[u];i+=1){
    v=vertices_neighbor[u,i]
    if(ketemu(v)){
    alt=vertices_dist[u]+vertices_distb[u,i]
    if(alt<vertices_dist[v]){
      vertices_dist[v]=alt;
      vertices_prev[v]=u;
    }
    }
  }
  }
 }

/*
 Dijkstra's Algorithm


@> Function
 * To find a shortest path from starting vertex (s) to target vertex (t)
  and return path distance from s to t.

@> Required Data
 * n: number of grid vertices
 * s: index of source vertex
 * t: index of target vertex
 * global.nb[u,i]: i-th neighbor of grid vertex u, whose distance from u
                  is 1 (as vertex index)
 * global.tc[u,i]: terrain cost from u to global.nb[u,i]
                  (equal to 1 normally)
 * global.neighbors: maximum number of each vertices (usually 4 for
                    4-directional movement or 8 for 8-directional movement)

@> Required Scripts
 * remove(x): Removes x from array q (as priority queue)
 * add(x): Inserts x into array q (as priority queue)
 * u_nearest(): Returns index u of array q, where vertices_dist[u]
                is smallest

@> Usage Guide
 * For graph initialization, build a passage graph with script
  buildGraph().
 * Then use this script on a game character. Set its variables s as index of
  the target's position vertex and t as index of the character's
  position vertex.
 * After that, you can trace the character's path by using vertices_prev[t].
 * You can also use vertices_dist[t] or value returned by this script to
  show the character's distance to the target.

@> Credits
 * Bunga Tepi Jalan (bungatepijalan.wordpress.com)
 * Wikipedia

@> Notes
 * If you want to learn more about Dijkstra's algorithm, see the article at:
  http://en.wikipedia.org/wiki/Dijkstra's_algorithm
 * The path constructed by this algorithm is always the shortest.
 * This script is made based on pseudocode at that article, with
  improvement on efficiency.
*/

// Initializations
nq=0        // Create open list q (as priority queue)
add(s)      // Add s into open list q
for(i=1;i<=n;i+=1){
    vertices_dist[i]=9999 // Unknown distance function from source to v
    vertices_prev[i]=0    // Previous node in optimal path from source
}
vertices_dist[s]=0      // Distance from source to source
while(nq>0){            // The main loop
    //Finds vertex u with least value of path distance
    u_nearest()
    dist_u=vertices_dist[u]
    if(u==t){
        //If u is the target, search completed and returns its distance.
        //You can add statements here, usually to read/construct path
        return dist_u
    }
    remove(u)
    for(i=1;i<=global.neighbors;i+=1){
        v=global.nb[u,i]    // where v has not yet been removed from Q.
        if(v!=0){
            alt=dist_u+global.tc[u,i]
            if(alt<vertices_dist[v]){  // Relax (u,v)
                add(v)
                vertices_dist[v]=alt
                vertices_prev[v]=u
                buildpanah(v)
            }
        }
    }
}
//Statements below this will be executed if all remaining vertices
//are inaccessible from source. This means that target vertex is isolated
//from source vertex. Also means that vertices_dist[t]==9999.
//You can add them here, usually to alert that no path is found.