SHARE
TWEET

DijkstraAlgorithm

a guest Jan 18th, 2014 173 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. using UnityEngine;
  2. using System.Collections;
  3. using System.Collections.Generic;
  4.  
  5. public class DijkstraAlgorithm {
  6.  
  7.         public static Stack<GameObject> Dijkstra(GameObject[] Graph, GameObject source, GameObject target){
  8.  
  9.                 Dictionary<GameObject, float> dist = new Dictionary<GameObject, float>();
  10.                 Dictionary<GameObject, GameObject> previous = new Dictionary<GameObject, GameObject> ();
  11.                 List<GameObject> Q = new List<GameObject> ();
  12.  
  13.                 foreach (GameObject v in Graph) {
  14.                         dist[v]  = Mathf.Infinity;
  15.                         previous[v] = null;
  16.  
  17.                         Q.Add(v);
  18.                 }
  19.  
  20.                 dist[source] = 0;
  21.  
  22.                 while (Q.Count > 0) {
  23.  
  24.                         float shortestDistance = Mathf.Infinity;
  25.                         GameObject shortestDistanceNode = null;
  26.                         foreach(GameObject obj in Q){
  27.                                 if(dist[obj] < shortestDistance){
  28.                                         shortestDistance = dist[obj];
  29.                                         shortestDistanceNode = obj;
  30.                                 }
  31.                         }
  32.  
  33.                         GameObject u = shortestDistanceNode;
  34.                         Q.Remove(u);
  35.  
  36.                         // check to see if we made it to target
  37.                         if(u== target){
  38.                                 Stack<GameObject> S = new Stack<GameObject>();
  39.  
  40.                                 while(previous[u] != null){
  41.                                         S.Push(u);
  42.                                         u = previous[u];
  43.                                 }
  44.                                 return S;
  45.                         }
  46.  
  47.  
  48.                         if(dist[u] == Mathf.Infinity){
  49.                                 break;
  50.                         }
  51.  
  52.                         foreach(GameObject v in u.GetComponent<Node>().neighbors){
  53.                                 float alt = dist[u] + (u.transform.position - v.transform.position).magnitude;
  54.                                 if(alt < dist[v]){
  55.                                         dist[v] = alt;
  56.                                         previous[v] = u;
  57.                                 }
  58.                         }
  59.                 }
  60.                 return null;
  61.         }
  62. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top