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

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

79 Replies - 2628 Views - Last Post: 02 May 2014 - 07:29 PM Rate Topic: -----

#1 M-rhodes  Icon User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 131
  • 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.

Form load event code:

   private void Form1_Load(object sender, EventArgs e)
        {

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

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

            //Add the created buttons to the form
            foreach (Button temp in buttons)
            {
                this.Controls.Add(temp); //Add the button to the Form
            }

        }




ReadGraphFromTextFile Method

private void ReadGraphFromTextFile()
        {
             StringBuilder sb = new StringBuilder();
            using (StreamReader sr = new StreamReader("GraphFile.txt"))
            {
                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]));

                edges.Add(anEdge);
                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

            barrierVertexes.Add(tempVertex); //Store chosen barrier

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


        }



Images of the program:

Posted Image

Posted Image

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  Icon User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 131
  • 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)
                        {
                            tempVertexes.Add(tempVertex);
                            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
                tempEdges.Add(tempEdge);
            }







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

        }




Interface has been updated.
Posted Image

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

Was This Post Helpful? 0
  • +
  • -

#3 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10364
  • View blog
  • Posts: 38,390
  • 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.
Was This Post Helpful? 1
  • +
  • -

#4 M-rhodes  Icon User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 131
  • Joined: 24-September 10

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

Posted 29 April 2014 - 02:39 PM

View Postmacosxnerd101, 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.
Was This Post Helpful? 0
  • +
  • -

#5 M-rhodes  Icon User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 131
  • 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
   add v to F
   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!
Was This Post Helpful? 0
  • +
  • -

#6 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10364
  • View blog
  • Posts: 38,390
  • 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?
Was This Post Helpful? 0
  • +
  • -

#7 M-rhodes  Icon User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 131
  • Joined: 24-September 10

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

Posted 29 April 2014 - 03:40 PM

View Postmacosxnerd101, 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

Was This Post Helpful? 0
  • +
  • -

#8 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10364
  • View blog
  • Posts: 38,390
  • 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.
Was This Post Helpful? 1
  • +
  • -

#9 M-rhodes  Icon User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 131
  • Joined: 24-September 10

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

Posted 29 April 2014 - 05:06 PM

View Postmacosxnerd101, 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

View Postmacosxnerd101, 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();
        }

    }


Was This Post Helpful? 0
  • +
  • -

#10 M-rhodes  Icon User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 131
  • 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
                    {
                        PriorityQueue.Add(tempEdge); //Add edge to priority queue if connected to 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)

Posted Image

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

Was This Post Helpful? 0
  • +
  • -

#11 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10364
  • View blog
  • Posts: 38,390
  • 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.
Was This Post Helpful? 1
  • +
  • -

#12 M-rhodes  Icon User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 131
  • Joined: 24-September 10

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

Posted 29 April 2014 - 08:05 PM

View Postmacosxnerd101, 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! :)
Was This Post Helpful? 0
  • +
  • -

#13 M-rhodes  Icon User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 131
  • 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
                    {
                        PriorityQueue.Add(tempEdge); //Add edge to priority queue if connected to 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)

Posted Image
Was This Post Helpful? 0
  • +
  • -

#14 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 3453
  • View blog
  • Posts: 10,659
  • 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.

Merging threads...
Was This Post Helpful? 1
  • +
  • -

#15 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 3453
  • View blog
  • Posts: 10,659
  • 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.
Was This Post Helpful? 1
  • +
  • -

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