12,951,548 members (53,952 online)

#### Stats

123.1K views
78 bookmarked
Posted 31 Mar 2008

# A Fast Priority Queue Implementation of the Dijkstra Shortest Path Algorithm

, 4 Aug 2013 CPOL
Anyone needs a fast, efficient algorithm to compute the shortest path in C#? This article provides one.
 DataStructTest Backup DataStructTest Properties DataStructTest bin Debug DataStructTest.vshost.exe.manifest Properties DataStructTest.suo _UpgradeReport_Files UpgradeReport_Minus.gif UpgradeReport_Plus.gif DataStructTest.vshost.exe DataStructTest.vshost.exe.manifest Release DataStructTest.exe obj Debug Refactor TempPE Properties.Resources.Designer.cs.dll Release TempPE DataStructTest.suo UpgradeReport_Minus.gif UpgradeReport_Plus.gif ```using System; using System.Collections.Generic; using System.ComponentModel; using System.Data; using System.Drawing; using System.Text; using System.Windows.Forms; namespace DataStructTest { public partial class Form1 : Form { public Form1() { InitializeComponent(); } private int totalNodes=100000; private float[,] cost; private DijkstraFast dijkstra; private Random rv; private void Form1_Load(object sender, EventArgs e) { cost = new float[totalNodes, 4]; // initialize the cost matrix rv= new Random(); for (int i = 0; i < totalNodes; i++) { cost[i, 0] = (float)rv.Next(1000)*0.01f; cost[i, 1] = (float)rv.Next(1000) * 0.01f; cost[i, 2] = (float)rv.Next(1000) * 0.01f; cost[i, 3] = (float)rv.Next(1000) * 0.01f; } dijkstra = new DijkstraFast(totalNodes, new DijkstraFast.InternodeTraversalCost(getInternodeTraversalCost), new DijkstraFast.NearbyNodesHint(GetNearbyNodes)); } // a function to get relative position from one node to another private int GetRelativePosition(int start, int finish) { if (start - 1 == finish) return 0; else if (start +1 == finish) return 1; else if (start +5 == finish) return 2; else if (start -5 == finish) return 3; return -1; } // get costs. If there is no connection, then cost is maximum. private float getInternodeTraversalCost(int start, int finish) { int relativePosition = GetRelativePosition(start, finish); if (relativePosition < 0) return float.MaxValue; return cost[start, relativePosition]; } private IEnumerable GetNearbyNodes(int startingNode) { List nearbyNodes = new List(4); if (startingNode >= totalNodes-5) startingNode = -1; if (startingNode <=5) startingNode = -1; // in the order as defined in GetRelativePosition nearbyNodes.Add(startingNode-1); nearbyNodes.Add(startingNode+1); nearbyNodes.Add(startingNode+5); nearbyNodes.Add(startingNode-5); return nearbyNodes; } // compute private void button1_Click(object sender, EventArgs e) { int t1 = Environment.TickCount; int[] minPath = dijkstra.GetMinimumPath(int.Parse(textBox2.Text), int.Parse(textBox3.Text)); int t2 = Environment.TickCount; listBox1.Items.Clear(); for (int i = 0; i != minPath.Length; i++) listBox1.Items.Add(minPath[i]); int diff = (t2 - t1); MessageBox.Show("Path finding took "+diff.ToString()+" ms, Minimum item in list box: "+ minPath[minPath.Length-1].ToString()); } // initialize private void button2_Click(object sender, EventArgs e) { totalNodes=int.Parse(textBox1.Text); cost = new float[totalNodes, 4]; // initialize the cost matrix rv = new Random(); for (int i = 0; i < totalNodes; i++) { cost[i, 0] = (float)rv.Next(1000) * 0.01f; cost[i, 1] = (float)rv.Next(1000) * 0.01f; cost[i, 2] = (float)rv.Next(1000) * 0.01f; cost[i, 3] = (float)rv.Next(1000) * 0.01f; } dijkstra = new DijkstraFast(totalNodes, new DijkstraFast.InternodeTraversalCost(getInternodeTraversalCost), new DijkstraFast.NearbyNodesHint(GetNearbyNodes)); } } }```

If a file you wish to view isn't highlighted, and is a text file (not binary), please let us know and we'll add colourisation support for it.

## Share

 CEO Gravi Information Technologies and Consultancy Ltd Turkey
Currently, also an MSc. student in Technical University of Munich, I develop practical application in computer vision for more than 5 years. I design real-time solutions to industrial and practical vision problems, both 3D and 2D. Very interested in developing algorithms in C relating math and vision.