# [Q] How to implement the Dijkstra's algorithm in this situation

• (6 Pages)
• 1
• 2
• 3
• 4
• Last »

## 79 Replies - 5034 Views - Last Post: 02 May 2014 - 07:29 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'https://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=345935&amp;s=ec08b9270341dc23cbfa1142e2f9276c&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #16 M-rhodes

Reputation: 1
• Posts: 133
• Joined: 24-September 10

## Re: [Q] How to implement the Dijkstra's algorithm in this situation

Posted 30 April 2014 - 03:31 AM

Skydiver, on 29 April 2014 - 08:20 PM, said:

Please do not open new topics if they are related to an existing topic that you currently have. By actually adding on to your existing topic you help people not have to retread past questions and background information.

Ah ok, I created different topics as some questions were Algorithm specific or C# implementation specific. Guess it makes more sense for everything in one thread.

### #17 M-rhodes

Reputation: 1
• Posts: 133
• Joined: 24-September 10

## Re: [Q] How to implement the Dijkstra's algorithm in this situation

Posted 30 April 2014 - 07:41 AM

Update 4

Ran into a couple of problems with the Algorithm.

Note: All distances between Vertexes = 1

The Path that is taken is not legal.
For example, there are no diagonal connections. E should not be connected to I.

This is how the result looks

This is how the result should be

This post has been edited by M-rhodes: 30 April 2014 - 07:42 AM

### #18 M-rhodes

Reputation: 1
• Posts: 133
• Joined: 24-September 10

## Re: [Q] How to implement the Dijkstra's algorithm in this situation

Posted 30 April 2014 - 10:24 AM

Trying to follow the pseudo code example I provided. Still not getting anywhere :\

This the my algorithm code that I have based upon the pseudocode

``` // Dijkstra calculation algorithm
public void run(Graph aGraph, Vertex start, Vertex end)
{
Evaluate = start; //Set to the initial start vertex
End = end;

Vertex[] FinishedVertexes = new Vertex[aGraph.vertices.Count];

Edge edgeOfLeastDistance = new Edge(99, null, null, int.MaxValue);
int totaldistance = 0;
List<Vertex> visited = new List<Vertex>();

String path = ",";
bool finished = false;
bool firstvertex = false;
bool secondvertex = false;

for (int i = 0; i < aGraph.vertices.Count - 1; i++)
{
if (i != 0)
{
distances.Add(int.MaxValue); //Update all distances except first value to infinity

}
else
{
distances.Add(0); //Set the first distance value to 0 as it's the source distance
}

previous.Add(0); //Set all previous distances to 0

}

int j = 0; //Counter for adding vertexes to finished vertex list
while (FinishedVertexes[FinishedVertexes.Length - 1] == null)
{
foreach (Edge tempEdge in aGraph.edges) //for each edge in edges
{
if (tempEdge.FirstVertex.Equals(Evaluate)) //If the edge targets the evaluate vertex
{
}
if (tempEdge.FirstVertex.Equals(Evaluate) == false) //If the edge does not target the evaluate vertex
{
//Do not add to Priority Queue, break the foreach edge loop
}

}

//Add found vertex to finished vertexes
FinishedVertexes[j] = Evaluate;
//Determine the edge of lowest distance to the Evaluate vertex

foreach (Edge tempPriority in PriorityQueue)
{
//Relaxation
if (PriorityQueue.Count == 1)
{
FinishedVertexes[j + 1] = tempPriority.SecondVertex;
aGraph.edges.Remove(edgeOfLeastDistance);
}
else
{

if (tempPriority.DistanceCost < PriorityQueue[i + 1].DistanceCost) //If the new distance is lower than the edge of least distance
{

edgeOfLeastDistance = tempPriority; //Swap the lowest edge
previous[j] = tempPriority.DistanceCost; //Store the lowest distance
path = path + Evaluate.getID();
Evaluate = edgeOfLeastDistance.SecondVertex; //Evalute now set to the next targetted vertex on the edge
aGraph.edges.Remove(edgeOfLeastDistance);
break;
}
else
{
if (tempPriority.DistanceCost == PriorityQueue[i + 1].DistanceCost) //If the new distance is equal  than the edge of least distance
{

edgeOfLeastDistance = tempPriority; //Swap the lowest edge
previous[j] = tempPriority.DistanceCost; //Store the lowest distance
path = path + Evaluate.getID();
Evaluate = edgeOfLeastDistance.SecondVertex; //Evalute now set to the next targetted vertex on the edge
aGraph.edges.Remove(edgeOfLeastDistance);
break;
}

}
}

}
PriorityQueue = new List<Edge>(); //Destroy the old Priority Queue

j++;
}

}
}

```

This post has been edited by M-rhodes: 30 April 2014 - 10:58 AM

### #19 M-rhodes

Reputation: 1
• Posts: 133
• Joined: 24-September 10

## Re: [Q] How to implement the Dijkstra's algorithm in this situation

Posted 30 April 2014 - 11:08 AM

I've had an idea, should I have a starting edge, where the source points to itself e.g. Starting Edge = A,A,0. Then, select the two neighboring edges: Edge1 - A,B,1 and Edge2 - A,F,1.

```
if(edge1 < edge2)
{
edge0 = edge1;
}

```

### #20 M-rhodes

Reputation: 1
• Posts: 133
• Joined: 24-September 10

## Re: [Q] How to implement the Dijkstra's algorithm in this situation

Posted 30 April 2014 - 05:53 PM

I'm testing my algorithm, where the Source is A. However, the algorithm travels two the two connected nodes (B and F).

When the algorithm passes F, a null pointer exception occurs at the foreach statement:

The value of e when this happens is F, but states that there are no adjacencies.

Note: The PriorityQueue is a raw implementation of a Queue data structure, I chose this approach so that I could have complete control over the PriorityQueue.

(I will provide code for the Dijkstra Algorithm and the Priority Queue)

```               // Visit each edge exiting u
{
//code
}

```

Dijkstra operation

```        public void run(Vertex source, List<Vertex> vertexes)
{
source.minDistance = 0; //Set source distance to 0
PriorityQueue vertexQueue = new PriorityQueue(vertexes); //Create a new Priority Queue, pass in the List of vertexes
vertexQueue.Enqueue(source); //Add the source value to the

while (!vertexQueue.IsEmpty())
{
Vertex u = vertexQueue.Dequeue();

// Visit each edge exiting u
{
v = e.target;
double weight = e.weight;
double distanceThroughU = u.minDistance + weight;
if (distanceThroughU < v.minDistance)
{
vertexQueue.remove(v);
v.minDistance = distanceThroughU;
v.previous = u;
vertexQueue.Enqueue(v);
path = path + v.ID;
}
}
}

}

```

Priority Queue Code

```  class PriorityQueue
{

private readonly int maxsize = 25;
private Vertex[] vertexStore = new Vertex[24];
private List<Vertex> Vertexes;
private int tail = 0;
private int noOfItems;

public PriorityQueue()
{

}

public PriorityQueue(List<Vertex> vertexes) //Pass in the list of vertexes from the text file
{
int c = 0;
Vertexes = vertexes;
foreach (Vertex aVertex in vertexes)
{
this.vertexStore[c] = vertexes[c]; //Store elements from the List<Vertex> to the Vertex[]
noOfItems++; //Increment the number of items in the array
c++;
}

}
public void Enqueue(Vertex value) //Add a value to the array
{
noOfItems++; //increment number of items

vertexStore[tail] = value; //Store value at the tail

if (++tail == maxsize)
{
tail = 0;
}

}

public Vertex Dequeue() //Return a vertex
{
noOfItems--;

}
public void remove(Vertex aVertex) //Remove a vertex
{
for (int i = 0; i < noOfItems-1; i++)
{
if (aVertex.ID == Vertexes[i].ID) //Check the original list
{
Vertexes.RemoveAt(i); //modify original list
vertexStore = Vertexes.ToArray(); //pass to the array
noOfItems--; //decrement number of items
}

}
}
public Vertex Peek()
{
}

public bool IsEmpty() //is the array empty?
{

if (noOfItems == 0) //If there are no items
{
return true; //return true
}
else
{

return false; //return false
}

}

public bool IsFull() //if the array is full
{

if (noOfItems == maxsize)
{
return true;
}
else
{

return false;
}

}

}

```

### #21 Skydiver

• Code herder

Reputation: 6216
• Posts: 21,454
• Joined: 05-May 12

## Re: [Q] How to implement the Dijkstra's algorithm in this situation

Posted 30 April 2014 - 08:41 PM

Your path in post #17 would be very indicative that your adjacency matrix is messed up because you have edges that should not exist.

As for the null reference exception you noted in post #20, what does the debugger say? Which variable is null? u, u.adjacencies or something else?

### #22 Momerath

• D.I.C Lover

Reputation: 1021
• Posts: 2,463
• Joined: 04-October 09

## Re: [Q] How to implement the Dijkstra's algorithm in this situation

Posted 30 April 2014 - 09:01 PM

Your priority queue isn't a priority queue. Where in it do you order the items?

### #23 M-rhodes

Reputation: 1
• Posts: 133
• Joined: 24-September 10

## Re: [Q] How to implement the Dijkstra's algorithm in this situation

Posted 01 May 2014 - 02:25 AM

Skydiver, on 30 April 2014 - 08:41 PM, said:

Your path in post #17 would be very indicative that your adjacency matrix is messed up because you have edges that should not exist.

As for the null reference exception you noted in post #20, what does the debugger say? Which variable is null? u, u.adjacencies or something else?

It is the variable u.adjacencies. As the foreach loop is trying to access a null object from u.adjacencies.

To confirm, U is a vertex, and ".adacencies" is an edge list within the Vertex class, that stores the nearest neighbors and distances.

Momerath, on 30 April 2014 - 09:01 PM, said:

Your priority queue isn't a priority queue. Where in it do you order the items?

The items are already in an ordered list. The vertexes list contains 24 Vertex elements, each element ID corresponds with a letter from the Alphabet, vertexes[0] = Vertex.ID("A"), vertexes[1] = Vertex.ID("B") etc.

Should the Priority Queue only contain the source Vertex? and as the Algorithm is accessed, add the visited Vertexes (from vertexes) to the Priority Queue?

### #24 M-rhodes

Reputation: 1
• Posts: 133
• Joined: 24-September 10

## Re: [Q] How to implement the Dijkstra's algorithm in this situation

Posted 01 May 2014 - 04:51 AM

Seems as when the algorithm gets to node F, the adjacencies are null.
When in the input vertex array, F blatantly has adjacencies!

This post has been edited by M-rhodes: 01 May 2014 - 04:51 AM

### #25 Momerath

• D.I.C Lover

Reputation: 1021
• Posts: 2,463
• Joined: 04-October 09

## Re: [Q] How to implement the Dijkstra's algorithm in this situation

Posted 01 May 2014 - 05:42 AM

Your priority queue should have the edges ordered based on their length, shortest first. When an item is added to the queue it needs to be inserted in the proper spot, not just tacked on to the end.

### #26 Skydiver

• Code herder

Reputation: 6216
• Posts: 21,454
• Joined: 05-May 12

## Re: [Q] How to implement the Dijkstra's algorithm in this situation

Posted 01 May 2014 - 06:21 AM

The last time we saw your Vertex class was in post #9 where it didn't even have and adjacencies property. Can you show us your new implementation for that class, as well as, any relevant code that helps populate the that property?

### #27 M-rhodes

Reputation: 1
• Posts: 133
• Joined: 24-September 10

## Re: [Q] How to implement the Dijkstra's algorithm in this situation

Posted 01 May 2014 - 06:28 AM

Momerath, on 01 May 2014 - 05:42 AM, said:

Your priority queue should have the edges ordered based on their length, shortest first. When an item is added to the queue it needs to be inserted in the proper spot, not just tacked on to the end.

So, would I have a sort method within the add method of the Priority Queue? As a new vertex comes in, its distance is checked with other elements and sorted accordingly?

### #28 M-rhodes

Reputation: 1
• Posts: 133
• Joined: 24-September 10

## Re: [Q] How to implement the Dijkstra's algorithm in this situation

Posted 01 May 2014 - 06:33 AM

Skydiver, on 01 May 2014 - 06:21 AM, said:

The last time we saw your Vertex class was in post #9 where it didn't even have and adjacencies property. Can you show us your new implementation for that class, as well as, any relevant code that helps populate the that property?

Sure, the classes have changed dramatically. I have attached the GraphFile.txt which is used for reading in vertexes and associations.

Vertex class
```  public class Vertex
{
public String ID;
public double minDistance = Double.PositiveInfinity;
public Vertex previous;

public Vertex()
{

}

public Vertex(String argName)
{
ID = argName;
}
public String toString()
{
return ID;
}

public override bool Equals(object obj)
{
if (obj == null)
{
return false; //If the instance of the object is null, return false
}
else
{
Vertex other = obj as Vertex; //If the instance of the object is not null, pass into vertex variable

if (other == null)
{
return false; //If the vertex is null, return false

}
else
{

return other.ID == this.ID; //If the ID passed in matches the one required, return vertex

}
}
}
public override int GetHashCode()
{
return ID.GetHashCode();
}
}

```

Edge Class

``` public class Edge
{
public Vertex target;
public double weight;

public Edge(Vertex argTarget, double argWeight)
{
target = argTarget;
weight = argWeight;
}
}

```

Vertexes and Associations are read in from a text file (The i or comparions are made because, some vertexes only have 1 association)

```      private void ReadGraphFromTextFile()
{
Vertex TempVertex1;

StringBuilder sb = new StringBuilder();
{
String line;
// Read and display lines from the file until the end of
// the file is reached.
while ((line = sr.ReadLine()) != null)
{
sb.Append(line);
}
}
string allines = sb.ToString();
string[] array = allines.Split(',');
int j = 0;
for (int i = 0; i < array.Length - 1; i += 5)
{

if (i == 20 || i == 43 || i == 66 || i >= 89)
{
TempVertex1 = new Vertex(array[i]);

Vertex TempVertex2 = new Vertex(array[i + 1]);

int vertex2dist = Convert.ToInt32(array[i + 2]);

TempVertex1.adjacencies = new Edge[] { new Edge(TempVertex2, vertex2dist) };
i = i - 2;

}
else
{

TempVertex1 = new Vertex(array[i]);

Vertex TempVertex2 = new Vertex(array[i + 1]);

int vertex2dist = Convert.ToInt32(array[i + 2]);

Vertex TempVertex3 = new Vertex(array[i + 3]);

int vertex3dist = Convert.ToInt32(array[i + 4]);

TempVertex1.adjacencies = new Edge[]{ new Edge(TempVertex2, vertex2dist), //B
new Edge(TempVertex3, vertex3dist)};
}

}
}

```

How the Dijkstra algorithm is accessed (Click event of the run button)

```private void run_Click(object sender, EventArgs e)
{

Dijkstra dijkstra = new Dijkstra();

dijkstra.run(startingVertex, endVertex, vertexes);
}

```

#### Attached File(s)

This post has been edited by M-rhodes: 01 May 2014 - 06:34 AM

### #29 Skydiver

• Code herder

Reputation: 6216
• Posts: 21,454
• Joined: 05-May 12

## Re: [Q] How to implement the Dijkstra's algorithm in this situation

Posted 01 May 2014 - 06:51 AM

In your ReadGraphFromTextFile() method, you are instantiating TempVertex2 and TempVertex3 but not setting their adjacencies arrays. How do you know that alter in your code, you will never use Edge.target as a starting vertex where you assume that has the adjacencies arrays set.

I highly suggest that instead of instantiating the temporary vertices, you actually search for the existing vertices and use those references.

And a quick aside, modern C# code tends to frown on exposing member variables as public unless the the object is meant to be treated as a data transfer POCO.

### #30 M-rhodes

Reputation: 1
• Posts: 133
• Joined: 24-September 10

## Re: [Q] How to implement the Dijkstra's algorithm in this situation

Posted 01 May 2014 - 06:56 AM

Skydiver, on 01 May 2014 - 06:51 AM, said:

In your ReadGraphFromTextFile() method, you are instantiating TempVertex2 and TempVertex3 but not setting their adjacencies arrays. How do you know that alter in your code, you will never use Edge.target as a starting vertex where you assume that has the adjacencies arrays set.

I highly suggest that instead of instantiating the temporary vertices, you actually search for the existing vertices and use those references.

And a quick aside, modern C# code tends to frown on exposing member variables as public unless the the object is meant to be treated as a data transfer POCO.

The loop structure is used to assign TempVertex1 its adjacencies to TempVertex2 and TempVertex3.

The GraphFile.txt I have included would describe my method.
For example

A ---- TempVertex1
B,1 ---- TempVertex2 and its distance
F,1 ---- TempVertex3 and its distance