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

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

## 79 Replies - 5568 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=46ddb249a4e3ec769312da8cbeaa5b6d&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 M-rhodes

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

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

Posted 29 April 2014 - 10:44 AM

Hi guys,

I'm having trouble with how to implement the Dijkstra's algorithm with my Program. How do I send the start node, end node and barriers to the Dijkstra's algorithm?

EDIT: All distance values are pre-written in a text file, read in via streamreader and stored into a List of Edges.

Further information below

Firstly, the order of operation on the form load event is to:
-Get the nodes and edges from a Text file.
-Create the 24 on-screen nodes.
-Add the 24 on-screen buttons to the Form.

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

//Return vertexes (nodes) and Edges (associations) from Text file

//Create the A-Y buttons
createButtons();

//Add the created buttons to the form
foreach (Button temp in buttons)
{
}

}

```

```private void ReadGraphFromTextFile()
{
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 < 114; i += 3)
{
Edge anEdge = new Edge(j, array[i], array[i + 1], Convert.ToInt32(array[i + 2]));

debugrichtext.AppendText(anEdge.toString());
j++;
}
}

```

Secondly, if a button is clicked, the chosenNode, endNode and BarrierNodes are checked.

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

Button btn = sender as Button;

if (chosenNode == false)
{
createStartingNode(btn); //Create the starting node
}

if (endNode == false && btn.Text != startNodeID)
{
createEndNode(btn); //Create the end node
}

if (btn.Text != startNodeID && btn.Text != endNodeID && endNode == true)
{
createBarrierNode(btn); //Create the barrier node
}

}
```

Create starting node method

```  private void createStartingNode(Button btn)
{
btn.BackColor = Color.Green;

startingVertex = new Vertex(); //Create Starting Vertex
startingVertex.setID(btn.Text);

chosenNode = true;
startNodeID = btn.Text; //Store ID
startNodelbl.Text = startNodeID;
MessageBox.Show("Starting node " + btn.Text + " has been selected"); //Output  selection
}

```

Create End node method

```        private void createEndNode(Button btn)
{
btn.BackColor = Color.Red;
endNode = true;
endNodeID = btn.Text; //Store ID
endNodelbl.Text = endNodeID;

endVertex = new Vertex(); //Create Starting Vertex
endVertex.setID(btn.Text);

MessageBox.Show("End node " + btn.Text + " has been selected"); //Output selection

}

```

Create Barrier Node
```private void createBarrierNode(Button btn)
{

btn.BackColor = Color.Black;
Vertex tempVertex = new Vertex();
tempVertex.setID(btn.Text); //Get chosen barrier

selectedBarrierslbl.Text = selectedBarrierslbl.Text + btn.Text + ", "; //Output each selection

}

```

Images of the program:

All help is appreciated.

This post has been edited by M-rhodes: 29 April 2014 - 10:48 AM

Is This A Good Question/Topic? 0

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

### #2 M-rhodes

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

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

Posted 29 April 2014 - 01:04 PM

Update 3

I realised that all barrier vertex and barrier associations (edges) had to be removed from the Graph.
I have completed these removal methods.

Delete barrier vertexes was erroneous. Rewritten version below.
```private void deleteBarrierVertexes()
{
int c = 0;
int i = barrierVertexes.Count - 1;

List<Vertex> tempVertexes = new List<Vertex>();
//Remove Barrier nodes from the Graph

foreach (Vertex tempVertex in vertexes)
{
foreach (Vertex tempBarrier in barrierVertexes)
{
if (tempVertex.getID() == tempBarrier.getID())
{
c = 0;
break;
}
else
{
if (c == barrierVertexes.Count - 1)
{
c = -1;
}
}

c++;

}
}
vertexes = new List<Vertex>(tempVertexes); //replace the previous version of vertexes

}

```

Delete associations (edges) method

```        private void deleteAssociations()
{
int i = barrierVertexes.Count - 1;

List<Edge> tempEdges = new List<Edge>(); //List to store temporary edges

foreach (Edge tempEdge in edges)
{

foreach (Vertex tempBarrier in barrierVertexes)
{
if (tempEdge.FirstVertex == tempBarrier.getID())
{

debugrichtext.AppendText("Removed : " + tempEdge.toString() + " ");
}

if (tempEdge.SecondVertex == tempBarrier.getID())
{

debugrichtext.AppendText("Removed : " + tempEdge.toString() + " ");
}

}
//Legal edges (that do not contain barrier vertexes) are copied to the new array
}

edges = new List<Edge>(tempEdges); //replace the previous version of edges

}

```

Interface has been updated.

This post has been edited by M-rhodes: 29 April 2014 - 02:41 PM

### #3 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12772
• Posts: 45,967
• Joined: 27-December 08

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

Posted 29 April 2014 - 02:29 PM

So you really want an adjacency list model of some sort to model the relations. Then you have a starting vertex. You take each edge on the starting vertex and throw them into a priority queue. Poll the first edge and go to the neighboring vertex. Throw all its unvisited edges into the priority queue. Continue in this manner. Note that you update the distance to a vertex as you visit it.

Though it sounds like if you have barriers, you have a maze of some sort. So the A* algorithm might be a good alternative to consider.

### #4 M-rhodes

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

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

Posted 29 April 2014 - 02:39 PM

macosxnerd101, on 29 April 2014 - 02:29 PM, said:

So you really want an adjacency list model of some sort to model the relations. Then you have a starting vertex. You take each edge on the starting vertex and throw them into a priority queue. Poll the first edge and go to the neighboring vertex. Throw all its unvisited edges into the priority queue. Continue in this manner. Note that you update the distance to a vertex as you visit it.

Though it sounds like if you have barriers, you have a maze of some sort. So the A* algorithm might be a good alternative to consider.

Thanks for the feedback, the barrier nodes are completely removed from the vertex list and all previous edges relating to those vertexes are removed. I will add an update to describe my meaning.

### #5 M-rhodes

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

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

Posted 29 April 2014 - 03:32 PM

Hi guys,

I have four inputs: Vertex Start, Vertex End, List<Vertex> Vertices and List<Edge> Edges. Upon looking at psuedo-code examples, I cannot figure out how to apply these inputs to the Algorithm. This is the best psuedocode example that I have found. I can complete a run of Dijkstra's by hand, but when it comes to visualizing the Algorithm from a Programming perspective, I can't get my head around it.

```Given a graph, G, with edges E of the form (v1, v2) and vertices V, and a
source vertex, s

dist : array of distances from the source to each vertex
prev : array of pointers to preceding vertices
i    : loop index
F    : list of finished vertices
U    : list or heap unfinished vertices

/* Initialization: set every distance to INFINITY until we discover a path */
for i = 0 to |V| - 1
dist[i] = INFINITY
prev[i] = NULL
end

/* The distance from the source to the source is defined to be zero */
dist[s] = 0

/* This loop corresponds to sending out the explorers walking the paths, where
* the step of picking "the vertex, v, with the shortest path to s" corresponds
* to an explorer arriving at an unexplored vertex */

while(F is missing a vertex)
pick the vertex, v, in U with the shortest path to s
for each edge of v, (v1, v2)
/* The next step is sometimes given the confusing name "relaxation"
if(dist[v1] + length(v1, v2) < dist[v2])
dist[v2] = dist[v1] + length(v1, v2)
prev[v2] = v1
possibly update U, depending on implementation
end if
end for
end while
```

I appreciate the responses!

### #6 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12772
• Posts: 45,967
• Joined: 27-December 08

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

Posted 29 April 2014 - 03:36 PM

Quote

So you really want an adjacency list model of some sort to model the relations. Then you have a starting vertex. You take each edge on the starting vertex and throw them into a priority queue. Poll the first edge and go to the neighboring vertex. Throw all its unvisited edges into the priority queue. Continue in this manner. Note that you update the distance to a vertex as you visit it.

Per my response in your other thread, this is how I'd look at it.

Do you understand how an adjacency list is set up?

### #7 M-rhodes

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

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

Posted 29 April 2014 - 03:40 PM

macosxnerd101, on 29 April 2014 - 03:36 PM, said:

Quote

So you really want an adjacency list model of some sort to model the relations. Then you have a starting vertex. You take each edge on the starting vertex and throw them into a priority queue. Poll the first edge and go to the neighboring vertex. Throw all its unvisited edges into the priority queue. Continue in this manner. Note that you update the distance to a vertex as you visit it.

Per my response in your other thread, this is how I'd look at it.

Do you understand how an adjacency list is set up?

No, I haven't used them before. Looking on my code, I seemed to be on the right track. My Edge class takes stores: An ID, the ID of First Vertex, the ID of Second Vertex, and the Distance cost.

EDIT: I forgot to add, I was planning on using those ID's as references.

This post has been edited by M-rhodes: 29 April 2014 - 03:43 PM

### #8 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12772
• Posts: 45,967
• Joined: 27-December 08

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

Posted 29 April 2014 - 03:46 PM

I'd probably look at something along the lines:
```class Vertex{
List<Edge> edges;
}

class Edge{
private Vertex vertexOne, vertexTwo;
private int cost;
}

```

Then your Graph class can store a List<Vertex>. It could store a List<Edge> as well.

So you are traversing the graph like a linked list, but you see branching rather than linearity.

### #9 M-rhodes

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

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

Posted 29 April 2014 - 05:06 PM

macosxnerd101, on 29 April 2014 - 03:46 PM, said:

I'd probably look at something along the lines:
```class Vertex{
List<Edge> edges;
}

class Edge{
private Vertex vertexOne, vertexTwo;
private int cost;
}

```

Then your Graph class can store a List<Vertex>. It could store a List<Edge> as well.

So you are traversing the graph like a linked list, but you see branching rather than linearity.

Thank you for the response, I have made good progress with the Program. Just trying to work out on iterating through the Graph.

G

macosxnerd101, on 29 April 2014 - 03:46 PM, said:

I'd probably look at something along the lines:
```class Vertex{
List<Edge> edges;
}

class Edge{
private Vertex vertexOne, vertexTwo;
private int cost;
}

```

Then your Graph class can store a List<Vertex>. It could store a List<Edge> as well.

So you are traversing the graph like a linked list, but you see branching rather than linearity.

Thank you for the response, I have made good progress with the Program. Just trying to work out on iterating through the Graph.

Graph Class
``` class Graph
{
public List<Vertex> vertices;
public List<Edge> edges;

public Graph(List<Vertex> Vertices, List<Edge> Edges)
{
this.vertices = Vertices;
this.edges = Edges;
}

}

```

Edge class
``` class Edge
{
public int ID;
public Vertex FirstVertex;
public Vertex SecondVertex;
public int DistanceCost;

public Edge(int anID, Vertex firstVertex, Vertex secondVertex, int aCost)
{
this.ID = anID;

this.FirstVertex = firstVertex;
this.SecondVertex = secondVertex;
this.DistanceCost = aCost;
}

public String toString()
{
String Output;
String id = this.ID.ToString();
String distance = DistanceCost.ToString();

return Output = ("Edge: " + id + " Vertex: " + FirstVertex.getID() + " - " + SecondVertex.getID() + " distance is " + distance + " ");

}

}

```

Vertex Class

``` class Vertex
{
List<Edge> edges;

public String ID;

public void setID(String anID)
{
this.ID = anID;
}
public String getID()
{
return this.ID;
}

public override bool Equals(object obj)
{
if (obj == null) return false;
Vertex other = obj as Vertex;
if (other == null) return false;
return other.ID == this.ID;
}

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

}

```

### #10 M-rhodes

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

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

Posted 29 April 2014 - 07:59 PM

macosxnerd101, I took your advice and I have implemented a Priority Queue. However, it seems to be stuck on an infinite loop whenever barriers are placed (edges are removed).

This is the dijkstra method

```namespace DijkstraDemo
{
class Dijkstra
{
public Vertex Evaluate;
public Vertex End;
public List<Vertex> Vertices;
public List<Edge> edges;
//dist : array of distances from the source to each vertex
public List<int> distances = new List<int>();
//prev : array of pointers to preceding vertices
public List<int> previous = new List<int>();
//i    : loop index
public int i;
//F    : list of finished vertices
public List<Vertex> FinishedVertexes;
//U    : list or heap unfinished vertices
public List<Vertex> unfinishedVertexes = new List<Vertex>();

List<Edge> PriorityQueue = new List<Edge>();

public string[] pathTaken;

public int totalcost;
// Constructor
public Dijkstra()
{

}

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

Edge edgeOfLeastDistance = new Edge(99,null,null,int.MaxValue);
int totaldistance = 0;

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

while (!finished)
{

foreach (Edge tempEdge in aGraph.edges)
{
if (Evaluate.Equals(tempEdge.FirstVertex)) //Checking for edges of matching evaluate vertex
{
}

}
foreach (Edge tempEdge1 in PriorityQueue) //Iterate through Priority queue
{
if (tempEdge1.DistanceCost < edgeOfLeastDistance.DistanceCost) //If tempedge distance is less than edge of least distance
{
edgeOfLeastDistance = tempEdge1; //Store new least vertex
totaldistance = totaldistance + edgeOfLeastDistance.DistanceCost; //Store distance cost so far
path = path + edgeOfLeastDistance.FirstVertex.getID() + ","; //Store path so far

}
}
Evaluate = edgeOfLeastDistance.SecondVertex; //Set the next vertex in the edge to evaluate
edgeOfLeastDistance.setDistance(int.MaxValue); //reset edge of least distance to default infinite
PriorityQueue = new List<Edge>(); //Destroy the old priority queue

if(Evaluate.Equals(end)) //If the evaluate = end node
{
finished = true; //End while
}
}
path = path + end.getID(); //Store overall path
this.pathTaken = path.Split(','); //Store as characters
this.totalcost = totaldistance; //Store total distance covered
}
}

}

```

Result of A to Y (all edge distances are equal to one)

This post has been edited by M-rhodes: 29 April 2014 - 08:01 PM

### #11 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12772
• Posts: 45,967
• Joined: 27-December 08

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

Posted 29 April 2014 - 08:04 PM

You'd probably be better discussing implementation specific details in your C# thread. I'm not a C# guy and really don't have the time at the moment to really weed through your code. Perhaps someone in C# will be able to better help.

### #12 M-rhodes

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

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

Posted 29 April 2014 - 08:05 PM

macosxnerd101, on 29 April 2014 - 08:04 PM, said:

You'd probably be better discussing implementation specific details in your C# thread. I'm not a C# guy and really don't have the time at the moment to really weed through your code. Perhaps someone in C# will be able to better help.

Ok will do!

### #13 M-rhodes

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

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

Posted 29 April 2014 - 08:07 PM

I have implemented a Priority Queue. However, it seems to be stuck on an infinite loop whenever barriers are placed (edges are removed).

This is the dijkstra method

```namespace DijkstraDemo
{
class Dijkstra
{
public Vertex Evaluate;
public Vertex End;
public List<Vertex> Vertices;
public List<Edge> edges;
//dist : array of distances from the source to each vertex
public List<int> distances = new List<int>();
//prev : array of pointers to preceding vertices
public List<int> previous = new List<int>();
//i    : loop index
public int i;
//F    : list of finished vertices
public List<Vertex> FinishedVertexes;
//U    : list or heap unfinished vertices
public List<Vertex> unfinishedVertexes = new List<Vertex>();

List<Edge> PriorityQueue = new List<Edge>();

public string[] pathTaken;

public int totalcost;
// Constructor
public Dijkstra()
{

}

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

Edge edgeOfLeastDistance = new Edge(99,null,null,int.MaxValue);
int totaldistance = 0;

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

while (!finished)
{

foreach (Edge tempEdge in aGraph.edges)
{
if (Evaluate.Equals(tempEdge.FirstVertex)) //Checking for edges of matching evaluate vertex
{
}

}
foreach (Edge tempEdge1 in PriorityQueue) //Iterate through Priority queue
{
if (tempEdge1.DistanceCost < edgeOfLeastDistance.DistanceCost) //If tempedge distance is less than edge of least distance
{
edgeOfLeastDistance = tempEdge1; //Store new least vertex
totaldistance = totaldistance + edgeOfLeastDistance.DistanceCost; //Store distance cost so far
path = path + edgeOfLeastDistance.FirstVertex.getID() + ","; //Store path so far

}
}
Evaluate = edgeOfLeastDistance.SecondVertex; //Set the next vertex in the edge to evaluate
edgeOfLeastDistance.setDistance(int.MaxValue); //reset edge of least distance to default infinite
PriorityQueue = new List<Edge>(); //Destroy the old priority queue

if(Evaluate.Equals(end)) //If the evaluate = end node
{
finished = true; //End while
}
}
path = path + end.getID(); //Store overall path
this.pathTaken = path.Split(','); //Store as characters
this.totalcost = totaldistance; //Store total distance covered
}
}

}

```

Result of A to Y (all edge distances are equal to one)

### #14 Skydiver

• Code herder

Reputation: 7569
• Posts: 25,480
• Joined: 05-May 12

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

Posted 29 April 2014 - 08:20 PM

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.

### #15 Skydiver

• Code herder

Reputation: 7569
• Posts: 25,480
• Joined: 05-May 12

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

Posted 29 April 2014 - 08:28 PM

Ummm... with your code in post #13, the only way to break out of the while loop is if you get to the final node. Since there is no path to the final node, of course you'll have an infinite loop. One of the prerequisite assumptions of the algorithm that you are using is that it assumes that a path exists. You just nullified that assumption.