Dijkstra Algorithmus in C# (csharp)
Veröffentlicht am 08.06.2009 | Kommentar schreiben | Tags: csharp, windows, microsoft
Um in einem Graphen den kürzesten Weg von einem bestimmten Knoten aus zu finden, ist der Dijkstra Algorithmus der wohl bekannteste Algorithmus. Im Folgenden wird eine simple Implementierung in C# (csharp) vorgestellt.
Der Dijkstra Algorithmus kann auf einen Graphen angewendet werden der aus einer Menge Kanten und Knoten besteht. In diesem Fall werden die Kanten Edges und die Knoten Nodes genannt.
Eine Kante besteht immer aus einem Startknoten Origin und einem Endkonten Destination. Als erstes wird diese Datenstruktur implementiert. Hierzu sind die Inhalte der Dateien Edge.cs und Node.cs angegeben.
Hinweis: Get- und Set-Methoden sind hier weggelassen worden, befinden sich jedoch im .zip-Archiv am Ende dieses Artikels
Edge.cs
using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace Programm { class Edge { private Node _origin; private Node _destination; private double _distance; /// <summary> /// Konstruktor /// </summary> /// <param name="origin">Startknoten</param> /// <param name="destination">Zielknoten</param> /// <param name="distance">Distanz</param> public Edge(Node origin, Node destination, double distance) { this._origin = origin; this._destination = destination; this._distance = distance; } } }
Node.cs
using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace Programm { public class Node { private string _name; /// <summary> /// Konstruktor /// </summary> /// <param name="name">Name des Knotens</param> public Node(string name) { this._name = name; } } }
Dijkstra.cs
In der Dijkstra Klasse befindet sich der Algorithmus selbst. Eine detaillierte Beschreibung des Dijkstra-Algorithmus findet man auf wikipedia, Siehe weiterführende Links
using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace Programm { class Dijkstra { private List<Node> _nodes; private List<Edge> _edges; private List<Node> _basis; private Dictionary<string, double> _dist; private Dictionary<string, Node> _previous; /// <summary> /// Konstruktor /// </summary> /// <param name="edges">Liste aller Kanten</param> /// <param name="nodes">Liste aller Knoten</param> public Dijkstra(List<Edge> edges, List<Node> nodes) { Edges = edges; Nodes = nodes; Basis = new List<Node>(); Dist = new Dictionary<string, double>(); Previous = new Dictionary<string, Node>(); // Knoten aufnehmen foreach (Node n in Nodes) { Previous.Add(n.Name, null); Basis.Add(n); Dist.Add(n.Name, double.MaxValue); } } /// <summary> /// Berechnet die kürzesten Wege vom start /// Knoten zu allen anderen Knoten /// </summary> /// <param name="start">Startknoten</param> public void calculateDistance(Node start) { Dist[start.Name] = 0; while (Basis.Count > 0) { Node u = getNodeWithSmallestDistance(); if (u == null) { Basis.Clear(); } else { foreach (Node v in getNeighbors(u)) { double alt = Dist[u.Name] + getDistanceBetween(u, v); if (alt < Dist[v.Name]) { Dist[v.Name] = alt; Previous[v.Name] = u; } } Basis.Remove(u); } } } /// <summary> /// Liefert den Pfad zum Knoten d /// </summary> /// <param name="d">Zielknote<n/param> /// <returns></returns> public List<Node> getPathTo(Node d) { List<Node> path = new List<Node>(); path.Insert(0, d); while (Previous[d.Name] != null) { d = Previous[d.Name]; path.Insert(0, d); } return path; } /// <summary> /// Liefert den Knoten mit der kürzesten Distanz /// </summary> /// <returns></returns> public Node getNodeWithSmallestDistance() { double distance = double.MaxValue; Node smallest = null; foreach (Node n in Basis) { if (Dist[n.Name] < distance) { distance = Dist[n.Name]; smallest = n; } } return smallest; } /// <summary> /// Liefert alle Nachbarn von n die noch in der Basis sind /// </summary> /// <param name="n">Knoten</param> /// <returns></returns> public List<Node> getNeighbors(Node n) { List<Node> neighbors = new List<Node>(); foreach (Edge e in Edges) { if (e.Origin.Equals(n) && Basis.Contains(n)) { neighbors.Add(e.Destination); } } return neighbors; } /// <summary> /// Liefert die Distanz zwischen zwei Knoten /// </summary> /// <param name="o">Startknoten</param> /// <param name="d">Endknoten</param> /// <returns></returns> public double getDistanceBetween(Node o, Node d) { foreach (Edge e in Edges) { if (e.Origin.Equals(o) && e.Destination.Equals(d)) { return e.Distance; } } return 0; } } }
Beispiel Instanz
Die Beispiel Instanz ist der Dijkstra Seite auf wikipedia entnommen worden und kann dort auf einem Bild nach vollzogen werden.
Zunächst werden die Knoten erstellt und ein Dictionary (wie assioziatives Array) gespeichert um diese direkt ansprechen zu können. Danach werden anhand der Knoten die Kanten mit deren Distanzen erstellt.
Anschließend wird ein Objekt der Klasse Dijkstra erstellt und "A" als Startknoten definiert. Nach dem die Distanzen berechnet worden sind, wird der Pfad zum Knoten "F" ausgegeben.
using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace Programm { class Program { static void Main(string[] args) { Dictionary<string, Node> _dictNodes = new Dictionary<string, Node>(); _dictNodes.Add("A", new Node("A")); _dictNodes.Add("B", new Node("B")); _dictNodes.Add("C", new Node("C")); _dictNodes.Add("D", new Node("D")); _dictNodes.Add("E", new Node("E")); _dictNodes.Add("F", new Node("F")); List<Node> _nodes = new List<Node>(); foreach (Node n in _dictNodes.Values) { _nodes.Add(n); } List<Edge> _edges = new List<Edge>(); _edges.Add(new Edge(_dictNodes["A"], _dictNodes["B"], 7)); _edges.Add(new Edge(_dictNodes["A"], _dictNodes["C"], 14)); _edges.Add(new Edge(_dictNodes["A"], _dictNodes["D"], 9)); _edges.Add(new Edge(_dictNodes["B"], _dictNodes["A"], 7)); _edges.Add(new Edge(_dictNodes["B"], _dictNodes["D"], 10)); _edges.Add(new Edge(_dictNodes["B"], _dictNodes["E"], 15)); _edges.Add(new Edge(_dictNodes["C"], _dictNodes["A"], 14)); _edges.Add(new Edge(_dictNodes["C"], _dictNodes["D"], 2)); _edges.Add(new Edge(_dictNodes["C"], _dictNodes["F"], 9)); _edges.Add(new Edge(_dictNodes["D"], _dictNodes["C"], 2)); _edges.Add(new Edge(_dictNodes["D"], _dictNodes["A"], 9)); _edges.Add(new Edge(_dictNodes["D"], _dictNodes["B"], 10)); _edges.Add(new Edge(_dictNodes["D"], _dictNodes["E"], 11)); _edges.Add(new Edge(_dictNodes["E"], _dictNodes["B"], 15)); _edges.Add(new Edge(_dictNodes["E"], _dictNodes["D"], 11)); _edges.Add(new Edge(_dictNodes["E"], _dictNodes["F"], 6)); _edges.Add(new Edge(_dictNodes["F"], _dictNodes["C"], 9)); _edges.Add(new Edge(_dictNodes["F"], _dictNodes["E"], 6)); // Neues Objekt der Klasse Dijkstra erstellen Dijkstra d = new Dijkstra(_edges, _nodes); // Startknoten festlegen und Distanzen berechnen d.calculateDistance(_dictNodes["A"]); // Pfad zu einem bestimmten Knoten ausgeben List<Node> path = d.getPathTo(_dictNodes["F"]); if (path.Count > 0) { foreach (Node n in path) { Console.Write(n.Name + " "); } Console.WriteLine(""); } Console.WriteLine("Bitte eine Taste drücken"); Console.ReadKey(); } } }
- Downloads
Dijkstra-Program-CSharp.zip56 K
Hallo,
super Artikel, hat mir echt sehr weitergeholfen.
Mach weiter so!
lg
Der Artikel ist Weltklasse, da er sich auch praktisch mit der Implementierung des Dijkstra-Algorithmus befaßt.
Supe, hab ich sonst noch nirgends gefunden.
lg
Super hilfreich! Gut erklärt und gut aufgebaut, wirklich perfekt für Anfänger.
greez
Danke, hat mir sehr weitergeholfen!
i don't now German, but that was the best Dijkstra implementation I've seen so far, thank u : )