Вот образец, который я взбил, который, кажется, работает. Чтобы быть более эффективным, вам нужно реализовать минимальную кучу при поиске следующего кратчайшего расстояния.
private static int FindMin(int[,] indexWeights, Tuple<int, int> src, Tuple<int, int> dst)
{
List<Node> allNodes = new List<Node>(indexWeights.GetLength(0)*indexWeights.GetLength(1));
Node[,] graph = GenerateGraph(indexWeights, allNodes);
Queue<Node> queue = new Queue<Node>();
Node currentNode = graph[src.Item1, src.Item2];
// 0 ? or the weight value at the index? This was not too clear from your example
// Setting the starting distance to 0 means that a->b != b->a because the starting value
// at index b is not the same as the starting value at index a
currentNode.Distance = indexWeights[src.Item1, src.Item2];
queue.Enqueue(currentNode);
while (queue.Count > 0)
{
currentNode = queue.Dequeue();
currentNode.Visited = true;
if (currentNode.XCoord == dst.Item1 && currentNode.YCoord == dst.Item2)
break;
// Calculate tentative distances
foreach (Node neighbor in currentNode.Neighbors)
{
neighbor.Distance = Math.Min(neighbor.Distance,
currentNode.Distance + indexWeights[neighbor.XCoord, neighbor.YCoord]);
}
// Find the node with the minimum distance that hasn't been visited, and visit that next.
// A min-heap would be BEST for getting the next node, but I'll leave that as an exercise for you
Node nonVisitedMinNode = allNodes.Where(a => !a.Visited)
.Aggregate((currMin, currNode) => currMin.Distance < currNode.Distance ? currMin : currNode);
queue.Enqueue(nonVisitedMinNode);
}
return graph[dst.Item1, dst.Item2].Distance;
}
public class Node
{
public Node(int xCoord, int yCoord)
{
XCoord = xCoord;
YCoord = yCoord;
Distance = int.MaxValue;
Visited = false;
Neighbors = new List<Node>();
}
public int XCoord { get; set; }
public int YCoord { get; set; }
public int Distance { get; set; }
public bool Visited { get; set; }
public List<Node> Neighbors { get; set; }
}
public static Node[,] GenerateGraph(int[,] weight, List<Node> allNodes)
{
Node[,] nodes = new Node[weight.GetLength(0),weight.GetLength(1)];
for (int i = 0; i < weight.GetLength(0); i++)
{
for (int j = 0; j < weight.GetLength(1); j++)
{
nodes[i, j] = new Node(i, j);
allNodes.Add(nodes[i, j]);
}
}
// Couldn't think of a way to combine the two loops together to set neighbors
for (int i = 0; i < weight.GetLength(0); i++)
{
for (int j = 0; j < weight.GetLength(1); j++)
{
if (0 <= (i - 1))
nodes[i, j].Neighbors.Add(nodes[i - 1, j]);
if (weight.GetLength(0) > (i + 1))
nodes[i, j].Neighbors.Add(nodes[i + 1, j]);
if (0 <= (j - 1))
nodes[i, j].Neighbors.Add(nodes[i, j - 1]);
if (weight.GetLength(1) > (j + 1))
nodes[i, j].Neighbors.Add(nodes[i, j + 1]);
}
}
return nodes;
}
Я не мог придумать неуклюжий способ создания графика ... может быть, здесь уже слишком поздно. В любом случае, вам может понадобиться настроить инициализацию currentNode.Distance на основе того, что мы обсуждали в комментариях. [0] 0 в вашем примере, потому что это начальный индекс, или это потому, что значение 0 для начала? Если вы приведете другой пример, в котором начальный индекс имеет значение , а не , имеющее значение 0, тогда правила будет легче понять.