Grill My Dijkstra

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");
}
}
}

re: Grill My Dijkstra

If you mark one, remember the "number of marked" as a member variable,
forcing you not to iterate through all markedArray[] in
CountMarkedVertices() in Implement() -> will gain some speed.
I don't know about memory allocation in C# - go to c# group for that.
We cannot give hints about that, we only can give you conceptual
hints. A C# group should be your first choice.

If you like us better than them, we can easily change this ;)
-Gernot

re: Grill My Dijkstra

A_StClaire_@hotmail.com wrote:[color=blue]
> 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)[/color]
[snip]

According to the FAQ, your question is off-topic here because on-topic
posts are "answerable by looking into the C++ language definition as
determined by the ISO/ANSI C++ Standard document, and by planned
extensions and adjustments"
(http://www.parashift.com/c++-faq-lit....html#faq-5.9).

IOW, this group is explicitly limited to the C++ language (hence the
name comp.lang.c++). Your post is neither in the C++ language nor
really concerned with language issues (C++ or C#) to begin with. Thus
we cannot answer your question.

We would, however, be happy to critique your use of the *language* (but
not the algorithm) if you re-post your code in C++ rather than C#.

Cheers! --M

re: Grill My Dijkstra

A_StClaire_@hotmail.com wrote:[color=blue]
> 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)[/color]

If it's the *algorithm* you want to be critiqued on, you may be better
off in comp.programming than either the C++ or C# groups. If it's your
*implementation* for which you seek criticism, you're clearly off-base
in a newsgroup for a language that many of us probably don't even know.

--
Mike Smith