The implementation of Dijkstra's Algorithm gives incorrect results

I need help implementing the Dijkstra Algorithm and was hoping someone could help me. I have it so that it prints some routes, but does not fix the correct costs for the path.

Here is my node structure:

   class Node
    {
        public enum Color {White, Gray, Black};
        public string Name { get; set; } //city
        public List<NeighborNode> Neighbors { get; set; } //Connected Edges
        public Color nodeColor = Color.White;
        public int timeDiscover { get; set; }//discover time
        public int timeFinish { get; set; } // finish time

        public Node() 
        { 
            Neighbors = new List<NeighborNode>();
        }
        public Node(string n, int discover)
        {
            Neighbors = new List<NeighborNode>();
            this.Name = n;
            timeDiscover = discover;
        }


        public Node(string n, NeighborNode e, decimal m)
        {
            Neighbors = new List<NeighborNode>();
            this.Name = n;
            this.Neighbors.Add(e);
        }

    }

    class NeighborNode
    {
        public Node Name { get; set; }
        public decimal Miles { get; set; } //Track the miles on the neighbor node

        public NeighborNode() { }
        public NeighborNode(Node n, decimal m)
        {
            Name = n;
            Miles = m;
        }

    }

Here is my algorithm:

   public void DijkstraAlgorithm(List<Node> graph)
    {

        List<DA> _algorithmList = new List<DA>(); //track the node cost/positioning
        Stack<Node> _allCities = new Stack<Node>(); // add all cities into this for examination
        Node _nodeToExamine = new Node(); //this is the node we're currently looking at.
        decimal _cost = 0;

        foreach (var city in graph) // putting these onto a stack for easy manipulation. Probably could have just made this a stack to start
        {
            _allCities.Push(city);
            _algorithmList.Add(new DA(city));
        }

        _nodeToExamine = _allCities.Pop(); //pop off the first node

        while (_allCities.Count != 0) // loop through each city
        {

            foreach (var neighbor in _nodeToExamine.Neighbors) //loop through each neighbor of the node
            {
                for (int i = 0; i < _algorithmList.Count; i++) //search the alorithm list for the current neighbor node
                {
                    if (_algorithmList[i].Name.Name == neighbor.Name.Name) //found it
                    {
                        for (int j = 0; j < _algorithmList.Count; j++) //check for the cost of the parent node
                        {
                            if (_algorithmList[j].Name.Name == _nodeToExamine.Name) //looping through
                            {
                                if (_algorithmList[j].Cost != 100000000) //not infinity
                                    _cost = _algorithmList[j].Cost; //set the cost to be the parent cost

                                break;
                            }
                        }
                        _cost = _cost + neighbor.Miles;

                        if (_algorithmList[i].Cost > _cost) // check to make sure the miles are less (better path)
                        {
                            _algorithmList[i].Parent = _nodeToExamine; //set the parent to be the top node
                            _algorithmList[i].Cost = _cost; // set the weight to be correct
                            break;
                        }
                    }
                }

            }
            _cost = 0;
            _nodeToExamine = _allCities.Pop();
        }
    }

Here's what the graph looks like: enter image description here

List of node graphs essentially

Node - Neighboring Nodes

So for example:

Node = Olympia, neighboring nodes = Lacy and Tacoma

+5
source share
2 answers

I needed to rewrite the whole algorithm since it was not processed correctly:

    public void DijkstraAlgorithm(List<Node> graph)
    {

        List<DA> _algorithmList = new List<DA>(); //track the node cost/positioning
        DA _nodeToExamine = new DA(); //this is the node we're currently looking at.
        bool flag = true; //for exting the while loop later

        foreach (var node in graph)
        {
            _algorithmList.Add(new DA(node));
        }

        foreach (var children in _algorithmList[0].Name.Neighbors) //just starting at the first node
        {
            for (int i = 0; i < _algorithmList.Count; i++)
            {
                if (children.Name == _algorithmList[i].Name)
                {
                    _algorithmList[i].Parent = _algorithmList[0].Name;
                    _algorithmList[i].Cost = children.Miles;
                    _algorithmList[0].Complete = true;

                }
            }
        }

        while (flag) //loop through the rest to organize
        {
            _algorithmList = _algorithmList.OrderBy(x => x.Cost).ToList(); //sort by shortest path

            for (int i = 0; i < _algorithmList.Count; i++) //loop through each looking for a node that isn't complete
            {
                if (_algorithmList[i].Complete == false)
                {
                    _nodeToExamine = _algorithmList[i];
                    break;
                }
                if (i == 13) //if the counter reaches 13 then we have completed all nodes and should bail out of the loop
                    flag = false;
            }
            if (_nodeToExamine.Name.Neighbors.Count == 0) //set any nodes that do not have children to be complete
            {
                _nodeToExamine.Complete = true;
            }

            foreach (var children in _nodeToExamine.Name.Neighbors) //loop through the children/neighbors to see if there one with a shorter path
            {
                for (int i = 0; i < _algorithmList.Count; i++) 
                {
                    if (children.Name == _algorithmList[i].Name)
                    {
                        if (_nodeToExamine.Cost + children.Miles < _algorithmList[i].Cost) //found a better path
                        {
                            _algorithmList[i].Parent = _nodeToExamine.Name;
                            _algorithmList[i].Cost = _nodeToExamine.Cost + children.Miles;
                        }
                    }
                }
                _nodeToExamine.Complete = true;
            }
        }

        PrintDijkstraAlgoirthm(_algorithmList);
    }


    public void PrintDijkstraAlgoirthm(List<DA> _finalList)
    {
        foreach (var item in _finalList)
        {
           if (item.Parent != null)
                Console.WriteLine("{0} ---> {1}: {2}", item.Parent.Name, item.Name.Name, item.Cost);
        }
    }
0
source

I think the problem is that

_cost = _algorithmList[j].Cost; //set the cost to be the parent cost

You perform a direct assignment of value instead of adding old and new value.

Also, the fact that you do

if (_algorithmList[j].Cost != 100000000) //not infinity

, , , - , , .

, , , .

+4

All Articles