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

  • (6 Pages)
  • +
  • « First
  • 4
  • 5
  • 6

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

#76 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 02 May 2014 - 02:13 PM

I made the correction you suggested. All nodes are not visited. The output is the same as the form above.

Here is the list of visited nodes

EDIT: Also, some nodes have been repeatedly visited.

Posted Image

This post has been edited by M-rhodes: 02 May 2014 - 02:14 PM

Was This Post Helpful? 0
  • +
  • -

#77 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 3556
  • View blog
  • Posts: 11,027
  • Joined: 05-May 12

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

Posted 02 May 2014 - 02:21 PM

Why would the all the nodes have to be visited? The algorithm is supposed to stop if it gets to the end node.

Post your current code. Loading code and search code, please. Also post the relevant class member variable declarations.
Was This Post Helpful? 0
  • +
  • -

#78 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 02 May 2014 - 02:31 PM

Ok, will do. I thought every node had to be visited, I used this example as a reference for testing - http://qiao.github.i...ding.js/visual/

Loading the graph from Text file

Members
        List<Edge> edges = new List<Edge>(); //All of the edges (associations) on the Graph
        List<Vertex> vertexes = new List<Vertex>(); //All of the Vertexes (nodes) on the Graph
        List<Button> buttons = new List<Button>(); //Array of buttons (A-Y)
        List<Vertex> vertices = new List<Vertex>();
        Dictionary<string, Vertex> verticesDict = new Dictionary<string, Vertex>();
        Vertex aSearchVertex;
        Vertex v;
        static string[] vertexIDs = new string[] { "A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y"};

        Vertex startingVertex; //storing the starting vertex
        Vertex endVertex; //storing the end vertex

        List<Vertex> barrierVertexes = new List<Vertex>(); //storing the barrier/s

        bool chosenNode = false;
        bool endNode = false;


        string startNodeID = "";
        string endNodeID = "";



Loading code
  private void ReadGraphFromTextFile()
        {
            long number1;
            Vertex TempVertex1 = new Vertex();
            Vertex TempVertex2 = new Vertex();
            Vertex u = new Vertex();
            List<string> vertexNames = new List<string>();
            List<int> weights = new List<int>();



            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;
            int i = 0;


            int y = 0;
            int z = 3;
            List<Edge> edges = new List<Edge>();
            List<Vertex> vertexes = new List<Vertex>();
            //Find all vertex names and assign weights
            foreach (string edgeString in array)
            {
            
                string[] anEdge = edgeString.Split(',');

                foreach (string vertexName in anEdge)
                {
                    bool isNumeric = long.TryParse(vertexName, out number1); //Determines if the input is string or numeric
                    if (!isNumeric && !vertexNames.Contains(vertexName)) //if string and it should not already be stored in the array
                    {
                        vertexNames.Add(vertexName); //store to names
                    }
                    else
                    { //if int
                        int temp = Convert.ToInt32(number1);
                        weights.Add(temp); //Store to weights
                    }


                }
                string prev = "";
                string current = "";

                foreach (string vertexName in vertexNames) //for each vertex name in the vertex name array
                {
                    v = new Vertex() { ID = vertexName }; //create a new vertex
                    if (!vertices.Contains(v) || vertices.Count == 0) //If the vertex name key is not found or if there are no elements in vertices
                    {
                        
                       
                        vertices.Add(v); //add the vertex to the vertices dictionary
                   
                       
                        }
                }

                if (vertexNames[0] != "")
                {
                    
                    var tempv1 = new Vertex();
                    tempv1 = vertices[i];

                    var tempv2 = new Vertex();
                    tempv2 = vertices[i + 1];

                    var tempv3 = new Vertex();
                    tempv3 = vertices[i + 2];

                    tempv1.adjacencies.Add(new Edge(tempv2, weights[i]));
                    tempv1.adjacencies.Add(new Edge(tempv3, weights[i + 2]));

                    vertexes.Add(tempv1);
                   if (!verticesDict.ContainsKey(tempv1.ID))
                   {



                       verticesDict.Add(tempv1.ID, tempv1);


                   }
                    vertexNames = new List<string>();
                    vertices = new List<Vertex>();
                }else{
                    break;
                    
                }

            }



Dijkstra Code
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace DijkstraDemo
{


    public class Dijkstra
    {
        

        private Vertex v = new Vertex();
        Vertex u;
        Dictionary<string, Vertex> verticesDict = new Dictionary<string, Vertex>();
        public List<string> visited = new List<string>();
        static string[] vertexIDs = new string[] { "A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y" };
        List<double> dist = new List<double>();
        private List<Vertex> Q = new List<Vertex>();
        private List<Vertex> Previous = new List<Vertex>();
        bool finished = false;
        public Dijkstra()
        {
    
        }



        public void run(Vertex source, Vertex end, Dictionary<string, Vertex> aVerticesDict)
        {
            double inf = double.PositiveInfinity;
            verticesDict = aVerticesDict;
            for(int i = 0; i < aVerticesDict.Count;i++)
            {
                var tv = new Vertex();
                verticesDict.TryGetValue(vertexIDs[i], out tv);
                if (tv == source)
                {
                    tv.minDistance = 0; //set source vertex to 0
            
                    Q.Add(tv);
                }
                else
                {
                    //tv.minDistance = inf; //sets the distance from source to infinite
          
                    Q.Add(tv); //add the vertex
                }

             }
           
            int j = 0;
            
            
            while (Q.Count != 0)
            {
               u = Q[0];
                Q.Remove(u);

        
                // Visit each edge on the u vertex
                    foreach (Edge e in u.adjacencies)
                    {
                        Vertex v = e.Target;
                        if (v == null) //vertex not found
                        {

                        }
                        else
                        {
                            u.minDistance = 0;
                            double weight = e.weight;
                            double distanceThroughU = u.minDistance + weight;


                            double alt = u.minDistance + 1;



                            if (alt < v.minDistance)
                            {

                                dist.Add(distanceThroughU);

                                visited.Add(v.ID);
                                Q.Remove(v); //Remove vertex
                                List<Vertex> SortedList = Q.OrderBy(o => o.minDistance).ToList(); //Sort the list Q
                                Q = SortedList; //Replace Q
                            }
                        }

                        if (v == end)
                        {

                            break;
                        }
                        else
                        {
                           
                        }
                    }

                    }
                }
            }
            }


       






This is the run button click event

 private void button29_Click(object sender, EventArgs e)
        {
            if (barrierVertexes.Count != 0)
            {
                //deleteBarrierVertexes(); //delete all the barrier vertexes
                // deleteAssociations(); //delete all the association/s to the barriers
            }


            Dijkstra dijkstra = new Dijkstra();

            dijkstra.run(startingVertex, endVertex, verticesDict);

            foreach (string s in dijkstra.visited)
            {
                    debugrichtext.AppendText("Nodes Visited : " + s + "\r\n");
                foreach (Control aControl in Controls)
            {
                if(aControl is Button)
                {
                    if (aControl.Text != endNodeID)
                    {

                        switch (aControl.Text == s)
                        {
                            case true:
                                aControl.BackColor = Color.Cyan;
                                this.Controls.Add(aControl);

                                break;
                            case false:

                            default:

                                break;

                        }
                    }
            }


This post has been edited by M-rhodes: 02 May 2014 - 02:34 PM

Was This Post Helpful? 0
  • +
  • -

#79 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 3556
  • View blog
  • Posts: 11,027
  • Joined: 05-May 12

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

Posted 02 May 2014 - 07:05 PM

Problems with your ReadGraphFromTextFile()
Lines 12-24: As I previously stated, you could have simply used File.ReadAllLines(), and you wouldn't have needed the '.' at the end of each line. In other words like 34 could simply have been:
foreach(string edgeString in File.ReadAllLines("GraphFile.txt"))


or even better less memory bloat:
foreach(string edgeString in File.ReadLines("GraphFile.txt"))



Lines 39-53: Since each of your lines is fixed format, this could have been simplified as something like this pseudo-code:
AddIfNotPresent(vertexNames, anEdge[0]);
AddIfNotPresent(vertexNames, anEdge[1]);
weights.Add(int.Parse(anEdge[2]));


with a helper method:
void AddIfNotPresent<T>(List<T> list, T item)
{
    if (!list.Contains(item))
        list.Add(item);
}



Line 60: This condition will always be true. You are creating a brand new instance of a vertex on line 59. There is no way that brand new instance will be present in your vertices list, so !vertices.Contains(v) will always be true so you'll always be adding an item into the vertices list. More on this in the next comment about lines 59-67.

Lines 59-67: On lines 39-53, you had ensured the only unique names made it into the vertexNames array. So this means that this could be simplified to just add vertices directly:
vertices.Add(new Vertex() { ID = vertexName });



Lines 73, 76, 79: Why are you instantiating Vertex()'s that you just end up not using on the succeeding lines 74, 77, 80?

Line 80: WTF!!!! Did you change your file format again? In post #43 you said that each line was:
vertexA, vertexB, weightAB.


If that's the case, how are you getting a 3rd vertex in the vertices list?

Line 95-96: WTF!!! Why are you blowing away your list of vertices and vertex names? Oh, it's because back in lines 74, 75, 80, i is always 0. Why is it always 0? It's because you are always creating new Vertex instances, again. *sigh* You are back again to essentially using TempVertex2 and TempVertex3 again, but this time it's vertices[i + 1] and vertices[i + 2]. *sigh*
Was This Post Helpful? 0
  • +
  • -

#80 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 3556
  • View blog
  • Posts: 11,027
  • Joined: 05-May 12

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

Posted 02 May 2014 - 07:29 PM

I hate to say this, but if you don't understand how class instances and object references work, you may be better off transliterating the pseudo code in the Wikipedia article using just plain old arrays and making sure that vertices have vertex numbers (e.g. 0, 1, 2, etc.) instead of vertex labels (e.g. "A", "B", "C", etc.)
Was This Post Helpful? 0
  • +
  • -

  • (6 Pages)
  • +
  • « First
  • 4
  • 5
  • 6