Click here to Skip to main content
15,891,951 members
Articles / Desktop Programming / WPF

Dijkstra's Minimum Distance

Rate me:
Please Sign up or sign in to vote.
4.80/5 (34 votes)
27 May 2012GPL36 min read 69.1K   5.7K   82  
A .NET implementation of Dijkstra’s for finding the minimum distance path between two nodes in a connected, undirected graph.
using System;
using System.Collections.Generic;
using System.Text;
using System.Windows;
using System.Windows.Media;

namespace MinDistanceWpf.Classes
{
    public class Node:IComparable<Node>
    {
        private Point _drawingLocation;
        private Point _center;
        private string _label;
        private double _diameter;
        private bool _visited;
        private double _totalCost;

        private List<Edge> _edges;
        private Edge _edgeCameFrom;

        public Node(Point location, string label, double diameter)
        {
            this._drawingLocation = location;
            this._label = label;
            this._diameter = diameter;

            _visited = false;

            _edges = new List<Edge>();
            _totalCost = -1;
        }

        public Node(Point location, Point center, string label, double diameter)
            :this(location,label,diameter)
        {
            this._center = center;
        }

        public Point Location
        {
            get { return _drawingLocation; }
        }

        public Point Center
        {
            get { return _center; }
            set { this._center = value; }
        }

        public double Diameter
        {
            get { return _diameter; }
        }

        public string Label
        {
            get { return _label; }
        }

        public double TotalCost
        {
            get { return _totalCost; }
            set { this._totalCost = value; }
        }

        public List<Edge> Edges
        {
            get { return this._edges; }
            set { this._edges = value; }
        }

        public Edge EdgeCameFrom
        {
            get { return this._edgeCameFrom; }
            set { this._edgeCameFrom = value; }
        }

        /// <summary>
        /// Calculates whether the node contains a specific point.
        /// </summary>
        /// <param name="p">The point for which we are checking</param>
        /// <returns>true or false</returns>
        public bool HasPoint(Point p)
        {
            double xSq = Math.Pow(p.X - _center.X,2);
            double ySq = Math.Pow(p.Y - _center.Y,2);
            double dist = Math.Sqrt(xSq + ySq);

            return (dist <= (_diameter/2));
        }

        public bool Visited
        {
            get { return _visited; }
            set { this._visited = value; }
        }

        public int CompareTo(Node n)
        {
            return this._totalCost.CompareTo(n.TotalCost);
        }

        public void Reset()
        {
            _visited = false;
            _edgeCameFrom = null;
            _totalCost = -1;
        }
    }
}

By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.

If a file you wish to view isn't highlighted, and is a text file (not binary), please let us know and we'll add colourisation support for it.

License

This article, along with any associated source code and files, is licensed under The GNU General Public License (GPLv3)


Written By
Software Developer
Bulgaria Bulgaria
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.

Comments and Discussions