Shortest path in Directed Acyclic Graph

Question

I am given a string of characters, in which every consequent pair of characters comprises an edge. What I mean by that is this is the string: ABBCAD. Edges of the string are:

A->B
B->C
A->D

Shortest path distance is A->D

The task at hand is to build up a Directed Acyclic Graph in memory from the string using the above rule and find the shortest path staring at the root node(in the example given it's A label) ending at terminal node.

NJKUUGHBNNJHYAPOYJHNRMNIKAIILFGJSNAICZQRNM

I gather one of the approaches that suites the task is to use the Depth First Search algo.

This is not homework...

Answer 1

This is a job for Djikstra's Algorithm. Once you build a representation of your graph it should be easy enough to produce the lowest cost traversal ... since in your case it seems that all paths have an equal cost (1).

You can look here on CodeProject for a reasonably decent implementation of Djikstra in C#.

could you present me with a pseudo code of your version of the graph representation for this case?

There are multiple ways to represent a graph in such a problem. If the number of vertices in your graph are likely to be small - it would be sufficient to use an adjacency matrix for the representation of edges. In which case, you could just use a .NET multidimensional array. The trick here is that you need to convert vertices labelled with characters to ordinal values. One approach would be to write a wrapper class that maps character codes to indices into the adjacency matrix:

class AdjacencyMatrix
{
    // representation of the adjacency matrix (AM)
    private readonly int[,] m_Matrix;
    // mapping of character codes to indices in the AM
    private readonly Dictionary<char,int> m_Mapping;

    public AdjacencyMatrix( string edgeVector )
    {
        // using LINQ we can identify and order the distinct characters
        char[] distinctChars = edgeVector.Distinct().OrderBy(x => x);

        m_Mapping = distinctChars.Select((c,i)=>new { Vertex = c, Index = i })
                                 .ToDictionary(x=>x.Vertex, x=>x.Index);

        // build the adjacency cost matrix here...
        // TODO: I leave this up to the reader to complete ... :-D
    }

    // retrieves an entry from within the adjacency matrix given two characters
    public int this[char v1, char v2]
    {
        get { return m_Matrix[m_Mapping[v1], m_Mapping[v2]];
        private set { m_Matrix[m_Mapping[v1], m_Mapping[v2]] = value; }
    }
}

Answer 2

For this particular case, Dijkstra's could be greatly simplified. I imagine something like this would do the trick.

class Node {
    public object Value;

    // Connected nodes (directed)
    public Node[] Connections;

    // Path back to the start
    public Node Route;
}

Node BreadthFirstRoute(Node[] theStarts, Node[] theEnds) {
    Set<Node> visited = new Set<Node>();

    Set<Node> frontier = new Set<Node>();
    frontier.AddRange(theStarts);

    Set<Node> ends = new Set<Node>();
    ends.AddRange(theEnds);

    // Visit nodes one frontier at a time - Breadth first.
    while (frontier.Count > 0) {

        // Move frontier into visiting, reset frontier.
        Set<Node> visiting = frontier;
        frontier = new Set<Node>();

        // Prevent adding nodes being visited to frontier
        visited.AddRange(visiting);

        // Add all connected nodes to frontier.
        foreach (Node node in visiting) {               
            foreach (Node other in node.Connections) {
                if (!visited.Contains(other)) {
                    other.Route = other;
                    if (ends.Contains(other)) {
                        return other;
                    }
                    frontier.Add(other);
                }
            }
        }
    }

    return null;
}