مشکل برنامه دایجسترا
سلام. مشکل این برنامه چیه؟؟
using System;using System.Collections.Generic;
using System.Collections;
using System.Linq;
using System.Text;
namespace dijkstra
{
class Program
{
static List<node> Nodes = new List<node>();
static Dictionary<string, int> NodesIndex = new Dictionary<string, int>();
static List<edge> Edges = new List<edge>();
static int SizeEdges = 0;
static int SizeNodes = 0;
static string StartNode;
class node
{
public string name;
public string pre;
public int Dist;
public bool vis;
public node(string NodeName)
{
name = NodeName;
Dist = -1;
vis = false;
}
}
static public void AddNode(string NodeName)
{
node temp = new node(NodeName);
Nodes.Add(temp);
NodesIndex.Add(NodeName, Nodes.Count() - 1);
}
class edge
{
public string N1;
public string N2;
public int Dist;
public edge(string Node1, string Node2, int EdgeVal)
{
N1 = Node1;
N2 = Node2;
Dist = EdgeVal;
}
}
static public void AddEdge(string Node1, string Node2, int EdgeVal)
{
edge temp = new edge(Node1, Node2, EdgeVal);
Edges.Add(temp);
}
static void SetStartNode(string name)
{
Nodes[NodesIndex[name]].Dist = 0;
SizeNodes = Nodes.Count();
SizeEdges = Edges.Count();
StartNode = name;
}
static int VisitClosetNode()
{
int index = 0;
int Dist = 0;
for (int i = 0; i < SizeNodes; ++i)
{
if (!Nodes[i].vis && Nodes.Dist >= 0)
{
Dist = Nodes[i].Dist;
index = i;
break;
}
}
for (int i = 0; i < SizeNodes; ++i)
{
if (Nodes[i].Dist < Dist && !Nodes.vis && Nodes[i].Dist >= 0)
{
Dist = Nodes[i].Dist;
index = i;
}
}
Nodes[index].vis = true;
return index;
}
static void GetAllAdjcentNodes(string N, List<string> AdjNodes)
{
for (int i = 0; i < SizeEdges; ++i)
{
if (Edges[i].N1 == N && !(Nodes[(NodesIndex[Edges.N2])].vis))
{
AdjNodes.Add(Edges[i].N2);
}
else if (Edges[i].N2 == N && !(Nodes[NodesIndex[Edges.N1]].vis))
{
AdjNodes.Add(Edges[i].N1);
}
}
}
static bool EdgeConnectsNodes(edge E, string N1, string N2)
{
return (E.N1 == N1 && E.N2 == N2 || E.N1 == N2 && E.N2 == N1);
}
static int GetDistance(string N1, string N2)
{
for (int i = 0; i < SizeEdges; ++i)
{
if (EdgeConnectsNodes(Edges[i], N1, N2))
{
return Edges[i].Dist;
}
}
return -1;
}
static int GetNumOfUnVisNodes()
{
int NOUVN = 0;
for (int i = 0; i < SizeNodes; ++i)
{
if (!Nodes[i].vis)
{
++NOUVN;
}
}
return NOUVN;
}
static void Dijkstras()
{
while (GetNumOfUnVisNodes() > 0)
{
node ClosetsNode = Nodes[VisitClosetNode()];
List<string> AdjNodes = new List<string>();
GetAllAdjcentNodes(ClosetsNode.name, AdjNodes);
int SizeAdj = AdjNodes.Count();
for (int i = 0; i < SizeAdj; ++i)
{
node AdjNode = Nodes[NodesIndex[AdjNodes[i]]];
int Distance = ClosetsNode.Dist + GetDistance(ClosetsNode.name, AdjNodes[i]);
if (AdjNode.Dist >= 0)
{
if (Distance < AdjNode.Dist)
{
AdjNode.Dist = Distance;
AdjNode.pre = ClosetsNode.name;
}
}
else
{
AdjNode.Dist = Distance;
AdjNode.pre = ClosetsNode.name;
}
}
}
}
static void GetPathTo(string N, List<string> Path)
{
string CN = N;
while (CN != StartNode)
{
string Temp = CN;
Path.Insert(0, Temp);
CN = Nodes[NodesIndex[CN]].pre;
}
Path.Insert(0, StartNode);
}
static void Main(string[] args)
{
AddNode("a");
AddNode("b");
AddNode("c");
AddNode("d");
AddNode("e");
AddNode("f");
AddNode("g");
AddEdge("a", "c", 10);
AddEdge("a", "d", 19);
AddEdge("b", "c", 4);
AddEdge("c", "d", 4);
AddEdge("b", "f", 41);
AddEdge("c", "e", 20);
AddEdge("e", "f", 17);
AddEdge("d", "g", 30);
AddEdge("g", "f", 4);
SetStartNode("a");
Dijkstras();
List<string> Path = new List<string>();
GetPathTo("f", Path);
int Size = Path.Count();
for (int i = 0; i < Size; ++i)
{
Console.WriteLine(Path[0]);
Path.Remove(Path[0]);
}
Console.Read();
}
}
}
پاسخ با نقل قول