All your bases are belong to Dijkstra

CATS, willing to get a hold of all the bases, asked Dijkstra to give him a hand designing the most powerful algorithm to reach all bases with the least distance travelled.

I tried to implement the Dijkstra's algorithm using TDD. This algorithm is designed to find the fastest route to reach all nodes of a graph. Right now, I'm concerned about if I implemented the algorithm with the good angle. I tested it (obviously) and all my tests passes, so I'm pretty confident the algorithm works, I'm just not sure if it's the way it should be written.

Those are the two classes I used to represent the graphs :

```
[DebuggerDisplay("{Name}")]
public class Node
{
public string Name { get; }
public ICollection Links { get; }

public Node(string name)
{
if (String.IsNullOrWhiteSpace(name)) throw new ArgumentNullException(nameof(name));

Name = name;
Links = new Collection();
}

public override bool Equals(object obj)
{
Node node = obj as Node;
if (node == null) return false;

return Name.Equals(node.Name);
}

public override int GetHashCode()
{
return Name.GetHashCode();
}

///
/// Creates links betwen two nodes
///
/// First node
/// Second node
/// Distance between nodes
/// There is no order in the nodes
public static void Join(Node a, Node b, int distance)
{
if (a == null) throw new ArgumentNullException("a");
if (b == null) throw new ArgumentNullException("b");

Link linkAToB = new Link(a, b, distance);
Link linkBToA = new Link(b, a, distance);

a.Links.Add(linkAToB);
b.Links.Add(linkBToA);
}
}

[DebuggerDisplay("({From.Name}) to ({To.Name}), Distance : {Distance}")]
public class Link
{
public Guid Id { get; } = Guid.NewGuid();

public Node From { get; }
public Node To { get; }
public int Distance { get; }

public Link(Node from, Node to, int distance)
{
if

I've been thinking this over for a while now and I'm pretty sure you're not implementing Dijkstra's algorithm (which is the shortest path between two nodes in a graph). It looks like you're computing a minimum spanning tree (set of edges connecting all nodes with minimal cost).

Some additional remarks:

-
Link is an odd name - more generally the term Edge is used for a connection of two nodes in a graph.

-
I think your abstraction is a bit too leaky - the algorithm needs to know quite a bit about the internals of the nodes and links (I'm referring to things like this link.To.Links.Where(l => !l.ConnectsSameNodes(link)).

I would stipulate you could implement a Graph object with the following public interface and still create independent graph algorithms:

class Graph : IEnumerable
{
    // adds an edge between two nodes with the provided cost
    // creates the nodes if not present
    public Graph AddEdge(TNode from, TNode to, int cost)
    {
    }

    // returns a list of nodes connected to the source via an edge and the associated cost
    public IEnumerable> GetEdges(TNode source)
    {
    }

    // plus IEnumerable implementation - enumerate all nodes in the graph
}

This has the advantages that:

• Users can define their own node types and associate any meta data they like with it.

• The internal implementation of how nodes and edges are stored is hidden from the user as they do not have to concern themselves with it - neither should they.

Update:

To make it clear and summarize the comments left by @BenAaronson as well: Dijkstra's algorithm as explained on wikipedia finds the shortest path between two nodes in a graph. In which case you would expect having to provide a start and a end node for the algorithm. If your goal was to find all shortest paths from a given node to any other node via Dijkstra then this isn't what you're doing.

A simple example would be this graph:

A -6-> D
  |      ^
  5      |
  |      1
  v      |
  B -2-> C

You algorithm yields the sequence A -> B, B -> C, C -> D with a total cost of 7 which is indeed the set of edges connecting all nodes with minimal cost. If you were to use Dijkstra's algorithm to compute all shortest paths from A to every other node you would get: A -> B, A -> B -> C, A -> D at cost 13 (if you do not count A -> B twice) since the path with the minimal cost from A to D is indeed the edge with cost 6.

So your implementation finds the set of all edges so that all nodes are connected with the minimal cost. This, as mentioned above, is typically called a minimum spanning tree for which several algorithms exist, most notably Prim's algorithm and Kruskal's algorithm.

I haven't checked it in detail but it looks like your algorithm essentially is an implementation of Kruskal's algorithm. So it's not entirely wrong - it just isn't the algorithm you set out to implement.

You could rename your implementation to KruskalSolverStrategy and try again with Dijkstra (if you need help with that then Stackoverflow would be the better place to ask since CodeReview is about reviewing existing code).

StackExchange Code Review Q#115001, answer score: 6