Plz Review My Dijkstra Implementation

A

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

Peter N Roth

what is ur question, exactly?
--
Grace + Peace,
Peter N Roth
Engineering Objects International
http://engineeringobjects.com
Home of Matrix.NET


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 = 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");
}
}
}
Click to expand...
 
I

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


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 = 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");
}
}
}
Click to expand...
 
A

A_StClaire_

Ignacio said:
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,
Click to expand...

yes to all of the above.
 
R

rossum

thoughts or criticism anyone?
Click to expand...

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
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads

b-tree 11
waveInOpen 64-bit 0
how to find all the partitions of any integer in four terms? 4
C# new comer question about System.NullReferenceException 3
Merge sort on Linked List 7
Invalid token .... Very Very simply program, why do I get this? 9
Why x64 app runs slower than x86 app ? 3
Changing Time Zone using Interop 0

Top