Feuerwehr

pathfinder.cs

class Pathfinder{
	public int Determine_distance(Node start, Node destination) {
		var min_distance_found = int.MaxValue;

		Find_paths (start, destination, 
		            new List<Edge> (),
		            ref min_distance_found);

		return min_distance_found;
	}
		
	void Find_paths(Node current, Node destination, List<Edge> path, ref int min_distance_found) {
		// Has the pathfinder reached the destination?
		if (current.Id == destination.Id) {
			var distance = path.Select (e => e.Distance).Sum ();
			if (distance < min_distance_found) min_distance_found = distance;
			return;
		}

		// Continue searching "down the street" from the current location
		foreach (var e in current.Edges) {
			if (path.Contains (e)) continue;
			path.Add (e);
			Find_paths (e.End, destination, path, ref min_distance_found);
			path.Remove (e);
		}
	}
}


public class Node {
	public string Id;
	public List<Edge> Edges = new List<Edge>();
}

public class Edge {
	public int Distance;
	public Node End;
}

This seems to be one of the rare occaisons where a ref parameter seems to help. It allows to return a result where a function result cannot be used - even without resorting to a global variable.

Check() cannot return a result as a function because the search needs to continue after a path to the destinatin has been found.