Grill My Dijkstra

[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.Contruct Matrix(l_Filena me);
}

public static void InitializeArray s()
{
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(CountMark edVertices() < nodes)
{
int closestVertex = SelectUnmarkedV ertexClosestToS ource(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 CountMarkedVert ices()
{
int counter = 0;

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

return counter;
}

public static int SelectUnmarkedV ertexClosestToS ource(int sourceNode)
{
int shortestDistanc eToSource = infinity;
int closestVertex = 0;

for(int i = 0; i < nodes; ++i)
{
if(unmarkedArra y[i] == true)
{
if(refMatrix[sourceNode - 1, i] < shortestDistanc eToSource)
{
shortestDistanc eToSource = 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'Pre v' refers to 'previous' or
'preceding' node." +
"\n\n\n\n") ;
ShowArray("Prev ");
}

public static void ShowArray(strin g arrayName)
{

switch(arrayNam e)
{
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(arrayNam e)
{
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");
}
}
}

[Gernot Frisch]

If you mark one, remember the "number of marked" as a member variable,
forcing you not to iterate through all markedArray[] in
CountMarkedVert ices() 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

[mlimber]

A_*********@hot mail.com wrote:

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)

[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

[Mike Smith]

A_*********@hot mail.com wrote:

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)

If it's the *algorithm* you want to be critiqued on, you may be better
off in comp.programmin g 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