Plz Review My Dijkstra Implementation

[A_StClaire_]

thoughts or criticism anyone?
using System;

namespace Dijkstra
{
public class Algorithm
{
private const int nodes = 10;
private const int labels = 10;
/* this implementation of Dijkstra's Algorithm assumes a 10 x 10
reference matrix of labels (edge values) 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 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 = 0; 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");
}
}
}

[Peter N Roth]

what is ur question, exactly?
--
Grace + Peace,
Peter N Roth
Engineering Objects International
http://engineeringobjects.com
Home of Matrix.NET
<A_*********@hotmail.com> wrote in message
news:11*********************@o13g2000cwo.googlegro ups.com...

thoughts or criticism anyone?
using System;

namespace Dijkstra
{
public class Algorithm
{
private const int nodes = 10;
private const int labels = 10;
/* this implementation of Dijkstra's Algorithm assumes a 10 x 10
reference matrix of labels (edge values) 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 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 = 0; 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");
}
}
}

[Ignacio Machin \( .NET/ C# MVP \)]

Hi,

Did you tried it? did you run a test and was ok?

IMO no a lot of people have time to debug it or check for correctness. Dont
get me wrong but we do have jobs to keep :)

Is this a homework? ;)

cheers,

--
Ignacio Machin,
ignacio.machin AT dot.state.fl.us
Florida Department Of Transportation
<A_*********@hotmail.com> wrote in message
news:11*********************@o13g2000cwo.googlegro ups.com...

thoughts or criticism anyone?
using System;

namespace Dijkstra
{
public class Algorithm
{
private const int nodes = 10;
private const int labels = 10;
/* this implementation of Dijkstra's Algorithm assumes a 10 x 10
reference matrix of labels (edge values) 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 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 = 0; 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");
}
}
}

[A_StClaire_]

Peter N Roth wrote:

what is ur question, exactly?

just whether anyone has comments from a performance or professionalism
point of view.

[A_StClaire_]

Ignacio Machin ( .NET/ C# MVP ) wrote:

Hi,

Did you tried it? did you run a test and was ok?

IMO no a lot of people have time to debug it or check for correctness. Dont
get me wrong but we do have jobs to keep :)

Is this a homework? ;)

cheers,

yes to all of the above.

[rossum]

On 7 Nov 2005 09:31:26 -0800, A_*********@hotmail.com wrote:

thoughts or criticism anyone?

1 You are not using documentation comments (///). At the very least,
everything that is declared public should have a documentation comment
so that the IDE can help users of your class. This helps reusability.

2 I see very little error handling code. How robust is your class?

3 You have hard coded values like the import filename and node count.
You may want to amend your class so that the users can override the
defaults if they want to.

4 Why use a low number like 10,000 as infinity? I think it would be
better to use the system defined maximum integer so there is less
chance of a real distance being greater than infinity.

5 You do a lot of scanning through arrays. Perhaps a foreach loop
might be clearer.
rossum

[snip code]
The ultimate truth is that there is no ultimate truth