I'm trying to implement a code to find the best path in a graph. I was able to develop the method with recursion and now I'm trying to implement using stack.
The problem is that I get an exception when I try to access .Min (), and this does not happen with recursion.
The rest of the code is working.
If you have other suggestions, I also thank
Here is the recursion and stack code
public KeyValuePair<int, List<GrafoNode>> AcharCaminho_recursao(GrafoNode inicio, GrafoNode fim)
{
var visitados = new List<GrafoNode>();
visitados.Add(fim);
return AcharCaminho_recursao(inicio, fim, visitados);
}
protected KeyValuePair<int, List<GrafoNode>> AcharCaminho_recursao(GrafoNode inicio, GrafoNode fim, List<GrafoNode> visitados)
{
var caminho = new List<GrafoNode>();
var caminhos = new SortedList<int, List<GrafoNode>>(); // caminhos possiveis
if (ReferenceEquals(fim, inicio)) // isso VAI ACONTECER por causa da recursão
{
caminho.Add(inicio);
return new KeyValuePair<int, List<GrafoNode>>(0, caminho);
}
foreach (var item in fim.Vizinhos)
{
if (!visitados.Contains(item)) // não pode voltar onde já foi
{
var node = (GrafoNode)item;
visitados.Add(node);
var pair = AcharCaminho_recursao(inicio, node, visitados); // RECURSÃO!!!
if (!pair.Equals(default(KeyValuePair<int, List<GrafoNode>>)))
// se o retorno da recursão não for "vazio"
{
pair.Value.Add(fim);
var dist = pair.Key + fim.Custos[node];
caminhos.Add(dist, pair.Value);
}
}
}
if (caminhos.Count > 0)
return caminhos.Min(); // seleciona o menor caminho dos selecionados
else
return default(KeyValuePair<int, List<GrafoNode>>);
}
public KeyValuePair<int, List<GrafoNode>> AcharCaminho_pilha(GrafoNode inicio, GrafoNode fim)
{
var caminhos = new SortedList<int, List<GrafoNode>>();
var visitados = new List<GrafoNode>();
var pilha = new Stack<GrafoNode>();
var custo = 0;
pilha.Push(fim);
while (pilha.Count >= 1)
{
var retiraPilha = true;
foreach (var item in pilha.Peek().Vizinhos)
{
if (!visitados.Contains(item))
{
var node = (GrafoNode)item;
visitados.Add(node);
custo += pilha.Peek().Custos[node];
pilha.Push(node);
if (item.Vizinhos.Contains(inicio))
{
pilha.Push(inicio);
custo += node.Custos[inicio];
var lista = pilha.ToList();
caminhos.Add(custo, lista);
pilha.Pop();
}
else
retiraPilha = false;
break;
}
}
if (retiraPilha)
pilha.Pop();
}
if (caminhos.Count > 0)
return caminhos.Min(); // seleciona o menor caminho dos selecionados; A EXCEÇÃO É LANÇADA AQUI
else
return default(KeyValuePair<int, List<GrafoNode>>);
}
Exception Details:
{"At least one object must implement IComparable."}
If necessary, I can provide more details on the implementation of the ClassPreference class.
Thank you!