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

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

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

#16 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 30 April 2014 - 03:31 AM

View PostSkydiver, 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.

Merging threads...


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

#17 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 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.

Posted Image

This is how the result looks
Posted Image

This is how the result should be
Posted Image

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

Was This Post Helpful? 0
  • +
  • -

#18 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 30 April 2014 - 10:24 AM

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

Forgot to add:

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
                    {
                        PriorityQueue.Add(tempEdge); //Add to the Priority Queue
                    }
                    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

Was This Post Helpful? 0
  • +
  • -

#19 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 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;
   }



Was This Post Helpful? 0
  • +
  • -

#20 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 30 April 2014 - 05:53 PM

I've made some headway.

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
                foreach (Edge e in u.adjacencies)
                {
                 //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
                foreach (Edge e in u.adjacencies)
                {
                    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 head = 0;
        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
        {
            Vertex headItem;
            noOfItems--;
            headItem = vertexStore[head];
            head++;

            return headItem;
        
        }
        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()
        {
            return vertexStore[head - 1];
        }

        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;
            }
        
        
        }


    }


Was This Post Helpful? 0
  • +
  • -

#21 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 3617
  • View blog
  • Posts: 11,269
  • 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?
Was This Post Helpful? 1
  • +
  • -

#22 Momerath  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1012
  • View blog
  • Posts: 2,444
  • 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?
Was This Post Helpful? 1
  • +
  • -

#23 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 01 May 2014 - 02:25 AM

View PostSkydiver, 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.

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

#24 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 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!

Posted Image

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

Was This Post Helpful? 0
  • +
  • -

#25 Momerath  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1012
  • View blog
  • Posts: 2,444
  • 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.
Was This Post Helpful? 1
  • +
  • -

#26 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 3617
  • View blog
  • Posts: 11,269
  • 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?
Was This Post Helpful? 1
  • +
  • -

#27 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 01 May 2014 - 06:28 AM

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

#28 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 01 May 2014 - 06:33 AM

View PostSkydiver, 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 Edge[] adjacencies;
    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();
            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 < 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)};
                }
                vertexes.Add(TempVertex1);


            }
        }




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

Was This Post Helpful? 0
  • +
  • -

#29 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 3617
  • View blog
  • Posts: 11,269
  • 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.
Was This Post Helpful? 0
  • +
  • -

#30 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 01 May 2014 - 06:56 AM

View PostSkydiver, 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 readFromGraphFile method reads in the Vertices and Associations

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

TempVertex1.adjacencies = tempVertex2,dist and tempVertex3,dist
Was This Post Helpful? 0
  • +
  • -

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