A
A_StClaire_
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 = infinity;
// no path exists
}
for(i = 0; i < nodes; ++i)
{
prevArray = 0;
// no nodes have predecessors
}
for(i = 0; i < nodes; ++i)
{
markedArray = false;
unmarkedArray = 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 = closestVertex - 1;
}
}
}
}
}
public static int CountMarkedVertices()
{
int counter = 0;
for(int i = 0; i < nodes; ++i)
{
if(markedArray == 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 == 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 + 1);
}
break;
case "Marked":
for(int i = 0; i < nodes; ++i)
{
Console.Write("Node {0}\t\t{1}\n", i + 1, markedArray);
}
break;
case "Unmarked":
for(int i = 0; i < nodes; ++i)
{
Console.Write("Node {0}\t\t{1}\n", i + 1, unmarkedArray);
}
break;
default:
break;
}
Console.Write("\n\n");
}
}
}
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 = infinity;
// no path exists
}
for(i = 0; i < nodes; ++i)
{
prevArray = 0;
// no nodes have predecessors
}
for(i = 0; i < nodes; ++i)
{
markedArray = false;
unmarkedArray = 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 = closestVertex - 1;
}
}
}
}
}
public static int CountMarkedVertices()
{
int counter = 0;
for(int i = 0; i < nodes; ++i)
{
if(markedArray == 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 == 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 + 1);
}
break;
case "Marked":
for(int i = 0; i < nodes; ++i)
{
Console.Write("Node {0}\t\t{1}\n", i + 1, markedArray);
}
break;
case "Unmarked":
for(int i = 0; i < nodes; ++i)
{
Console.Write("Node {0}\t\t{1}\n", i + 1, unmarkedArray);
}
break;
default:
break;
}
Console.Write("\n\n");
}
}
}