Grill My Dijkstra

Question posted by: A_StClaire_@hotmail.com (Guest) on November 7th, 2005 10:05 AM

implemented Dijkstra's algorithm as follows. plz pour on the negative
criticism cuz I know I have a ton to learn.

oh, before you flame me regarding the language, my class was told to do
this in C# but, what can I say, I just like you guys better than the
crowd in the C# newsgroup. ;o)


using System;

namespace Dijkstra
{
public class Algorithm
{
private const int refArrayRows = 10;
private const int refArrayColumns = 10;
/* this implementation of Dijkstra's Algorithm assumes a 10 x 10
reference matrix of labels is provided */

private const int startNode = 1;
private const int endNode = 10;
/* a second assumption is point one is our starting or "vantage"
point
and point ten is our end point */

private const int nodes = 10;

private const int labels = 10;
// edge values

private const int resultColumns = 2;
/* each node (first column) in the determined shortest path has one
predecessor (second column) */

private const int infinity = 10000;
// value 10,000 represents no edge / link between nodes

private static int [,] refMatrix = new int[nodes, labels];
private static int [] distArray = new int [labels];
private static int [] prevArray = new int [nodes];
private static bool [] markedArray = new bool [nodes];
private static bool [] unmarkedArray = new bool [nodes];

private Algorithm()
{
}

public static void ImportRefMatrix()
{
string l_Filename = "..\\..\\Matrix.DAT";
refMatrix = Import.ContructMatrix(l_Filename);
}

public static void InitializeArrays()
{
int i = 0;

for( ; i < labels; ++i)
{
distArray[i] = infinity;
// no path exists

}

for(i = 0; i < nodes; ++i)
{
prevArray[i] = 0;
// no nodes have predecessors

}

for(i = 0; i < nodes; ++i)
{
markedArray[i] = false;
unmarkedArray[i] = true;
}

markedArray[startNode - 1] = true;
unmarkedArray[startNode - 1] = false;
// starting point considered marked

// - 1 often used when dealing with array indexes (which begin at 0)

}

public static void Implement()
{

while(CountMarkedVertices() < nodes)
{
int closestVertex = SelectUnmarkedVertexClosestToSource(startNode);
markedArray[closestVertex - 1] = true;
unmarkedArray[closestVertex - 1] = false;

for(int i = 0; i < labels; ++i)
{
if(refMatrix[closestVertex - 1, i] < infinity)
// for each edge adjacent to closestVertex

{
if(refMatrix[startNode - 1, i] > refMatrix[startNode - 1,
closestVertex - 1] +
refMatrix[closestVertex - 1, i])
/* if distance from starting point to adjacent node exceeds
distance from
starting point to closestVertex plus distance from closestVertex
to adjacent
node */

{
refMatrix[startNode - 1, i] = refMatrix[startNode - 1,
closestVertex - 1] +
refMatrix[closestVertex - 1, i];
// update distance grid

prevArray[i] = closestVertex - 1;
}
}
}

}

}

public static int CountMarkedVertices()
{
int counter = 0;

for(int i = 0; i < nodes; ++i)
{
if(markedArray[i] == true) ++counter;
}

return counter;
}

public static int SelectUnmarkedVertexClosestToSource(int sourceNode)
{
int shortestDistanceToSource = infinity;
int closestVertex = 0;

for(int i = 0; i < nodes; ++i)
{
if(unmarkedArray[i] == true)
{
if(refMatrix[sourceNode - 1, i] < shortestDistanceToSource)
{
shortestDistanceToSource = refMatrix[sourceNode - 1, i];
closestVertex = i;
}
}
}

return ++closestVertex;
}

public static void ShowResults()
{
Console.Write("\nThe following chart shows all nodes on the
left.\n\nTheir precedessors " +
"are listed in the right column.\n\n'Prev' refers to 'previous' or
'preceding' node." +
"\n\n\n\n");
ShowArray("Prev");
}

public static void ShowArray(string arrayName)
{

switch(arrayName)
{
case "Prev":
Console.Write("Prev ");
break;
case "Marked":
Console.Write("Marked ");
break;
case "Unmarked":
Console.Write("Unmarked ");
break;
default:
Console.Write("Unknown array name.\n\n");
break;
}

Console.Write("Array\n--------------\n\n");

switch(arrayName)
{
case "Prev":

for(int i = 0; i < nodes; ++i)
{
Console.Write("Node {0}\t\t{1}\n", i + 1, prevArray[i] + 1);
}

break;
case "Marked":

for(int i = 0; i < nodes; ++i)
{
Console.Write("Node {0}\t\t{1}\n", i + 1, markedArray[i]);
}

break;
case "Unmarked":

for(int i = 0; i < nodes; ++i)
{
Console.Write("Node {0}\t\t{1}\n", i + 1, unmarkedArray[i]);
}

break;
default:
break;
}

Console.Write("\n\n");
}
}
}

Quote | Subscribe