У меня проблема с реализацией алгоритма Дейкстры с использованием списка смежности. Я много пробовал, но я не знаю, как его реализовать.
Это мой класс графов с использованием списка смежности
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace testMapRouting
{
#region Node Class
class Node
{
public double speed { get; set; }
public double time { get; set; }
public double distance { get; set; }
public double xCord;
public double yCord;
public int source { get; set; }
public int destenation { get; set; }
public Node() { }
public Node(int Source)
{
this.source = Source;
}
public Node(int Source,double _xOnMap,double _yOnMap)
{
this.xCord = _xOnMap;
this.yCord = _yOnMap;
this.source = Source;
this.speed = 5.0;
}
public Node(int SOURCE, int DESTENATION, double SPEED, double DISTANCE)
{
this.source = SOURCE;
this.destenation = DESTENATION;
this.speed = SPEED;
this.distance = DISTANCE;
this.time = this.distance / this.speed;
}
#region overRide
/// <summary>
/// Overriding the Equal Methos"same as =="
/// to Help me implement some functions
/// </summary>
public override bool Equals(object obj)
{
var item = obj as Node;
if (item == null)
{
return false;
}
return this.source.Equals(item.source);
}
public override int GetHashCode()
{
return this.source.GetHashCode();
}
#endregion
}
#endregion
#region Graph Class
class Graph<T> where T : IComparable<T>
{
#region Instance Variables
///<summary>
///Instance Variables
/// </summary>
///
private const long EMPTY_EDGE_VALUE = 0;
protected virtual int _edgeCount { get; set; }
public virtual Dictionary<Node, LinkedList<Node>> _adjacencyList { get; set; }
#endregion
#region Constructors
///<summary>
///Constructors
/// </summary>
///
public Graph()
{
_edgeCount = 0;
_adjacencyList = new Dictionary<Node, LinkedList<Node>>();
}
#endregion
#region main Functions
/// <summary>
/// add new edge to Graph
/// </summary>
/// <param name="source">source vertex</param>
/// <param name="Destenation">Destenation vertex</param>
/// <param name="speed"> Speed value</param>
/// <param name="Distance"> Distance value</param>
public void addEdge(Node source, Node Destenation, double speed, double Distance)
{
if (_adjacencyList.Count <= 0)
{
throw new InvalidOperationException("addEdge: There are no Vertices in Graph.\n");
}
else
{
if (_adjacencyList.ContainsKey(source) && _adjacencyList.ContainsKey(Destenation))
{
var sourceEdge = new Node(source.source, Destenation.source, speed, Distance);
var destenationEdge = new Node(Destenation.source, source.source, speed, Distance);
_adjacencyList[source].AddLast(sourceEdge);
_adjacencyList[Destenation].AddLast(destenationEdge);
++_edgeCount;
}
else
{
throw new NullReferenceException("addEdge : Source or Destenation Vetrtex Don't Exist in Graph.\n");
}
}
}
/// <summary>
/// add a new vertex to graph
/// </summary>
/// <param name="value"></param>
public void addVertex(Node value)
{
if (!_adjacencyList.ContainsKey(value))
{
LinkedList<Node> connections = new LinkedList<Node>();
_adjacencyList.Add(value, connections);
}
else
{
throw new InvalidOperationException("addVertex : This Vertex allready exists in Graph.\n");
}
}
#endregion
#region Utility Functions
///<summary>
///Utility Functions
/// </summary>
///<summary>
///return edges count in the Graph
/// </summary>
public int edgeCount()
{
return _edgeCount;
}
///<summary>
///return vertices count in the Graph
/// </summary>
public int verticesCount()
{
return _adjacencyList.Count;
}
//utility function to return the node with minimum
//time edge
// A utility function to print
// the constructed distance array
public void printSolution(double[] time, int n)
{
Console.Write("Vertex Distance " +
"from Source\n");
for (int i = 0; i < n; i++)
Console.Write(i + " \t\t " +
time[i] + "\n");
}
Проблема в этой функции, я не могу реализовать ее правильно, вы можете сказать мне, в чем проблема
public void dijkstra(Graph<T> myGraph,Node start,Node end)
{
bool[] shortestPath = new bool[_adjacencyList.Count];
double[] time = new double[_adjacencyList.Count];
SortedSet<int> queue = new SortedSet<int>(); //mafrod priority queue
int[] Parent = new int[_adjacencyList.Count];
for (int i = 0; i < _adjacencyList.Count; i++)
{
time[i] = int.MaxValue;
shortestPath[i] = false;
}
Parent[0] = -1;
time[start.source] = 0;
queue.Add(start.source);
for(int v = 0; v < _adjacencyList.Count - 1; v++)
{
//int u = Minimum_NodeTime(time,shortestpath);
int u = queue.Min();
shortestPath[u] = true;
Node tmp = new Node(u);
foreach (var node in _adjacencyList[tmp])
{
if (!shortestPath[v] && time[u] + node.time < time[v])
{
time[v] = time[u] + node.time;
Parent[v] = u;
}
}
}
printSolution(time, _adjacencyList.Count);
}
///<summary>
///Returns a list of vertices
/// </summary>
public List<Node> Vertices()
{
List<Node> Vert = new List<Node>();
foreach (var vertex in _adjacencyList)
{
Vert.Add(vertex.Key);
}
return Vert;
}
/// <summary>
/// Display Graph Content
/// </summary>
public void cout()
{
if (_adjacencyList.Count <= 0)
{
throw new InvalidOperationException("cout: Graph is empty.\n");
}
else
{
foreach (var vertex in _adjacencyList)
{
if (vertex.Value.Count <= 0)
{
Console.WriteLine("Vertex :" + vertex.Key.source.ToString() + " has Connections: ");
Console.WriteLine("cout: This vertex is disconnected.");
}
else
{
Console.WriteLine("##############################################");
Console.WriteLine("Vertex :" + vertex.Key.source.ToString() + " has Connections: ");
foreach (var node in vertex.Value)
{
Console.WriteLine("--------------------------------");
Console.WriteLine("Source : " + node.source.ToString());
Console.WriteLine("Destenation : " + node.destenation.ToString());
Console.WriteLine("Speed : " + node.speed.ToString());
Console.WriteLine("Distance : " + node.distance.ToString());
Console.WriteLine("Time : " + node.time.ToString());
Console.WriteLine("--------------------------------");
}
Console.WriteLine("##############################################");
}
}
}
}
#endregion
}
#endregion
}
Я смотрел на реализацию Дейкстры несколько раз, и я не знаю, что делать.