Find all paths from start node to the end node in a graph

Question

Here is my question.

I am trying to resolve this problem.

Given the start point and the end point, find all paths from start corner to the end corner. Include only routes which do not pass through any corner more than once.

For example: 1 is the start node, 6 is the end point. I have the the data as

The pairs of positive integers separated by blanks which are connected. So the output should be.

1 2 3 4 6
1 2 3 5 6
1 2 4 3 5 6
1 2 4 6
1 3 2 4 6
1 3 4 6
1 3 5 6

There are 7 routes from 1 to 6.

Now I use the graph search algorithm, I can only find one. And also I can't find the one given the final destination. I mean that I can only traversal the graph.

What I did was that I created the adjacency matrix of the graph then did a depth first search.

First I defined a class Node.

public class Node
{
    public string NodeId;
    public bool IsVisited;
    public Node(string nodeId)
    {
        NodeId = nodeId;
    }
}

Then the Graph class,

 public class Graph
{
    private Node[] _nodes;
    private int[][] _adjacencyMatrix;
    public int _numberOfTotalNodes;
    public Graph(int[][] adjacencyMatrix, int numberOfTotalNodes)
    {
        _adjacencyMatrix = adjacencyMatrix;
        _numberOfTotalNodes = numberOfTotalNodes;
        _nodes = new Node[_numberOfTotalNodes];
        for (int i = 0; i < _numberOfTotalNodes; i++)
        {
            _nodes[i] = new Node((i + 1).ToString());
        }
    }

    public void DepthFirstSearch()
    {
        Stack s = new Stack();
        _nodes[0].IsVisited = true;
        DisplayNodeId(0);
        s.Push(0);
        int v;
        while (s.Count > 0)
        {
            v = GetAdjUnvisitedNode((int)s.Peek());
            if (v == -1 || _nodes[v].IsVisited)
            {
                s.Pop();
            }
            else
            {
                _nodes[v].IsVisited = true;
                DisplayNodeId(v);
                s.Push(v);
            }
        }
        for (int u = 0; u < _numberOfTotalNodes; u++)
        {
            _nodes[u].IsVisited = false;
        }
    }

    public void DisplayNodeId(int nodePosition)
    {
        Console.Write(_nodes[nodePosition].NodeId + " ");
    }

    public int GetAdjUnvisitedNode(int v)
    {
        for (int j = 0; j < _numberOfTotalNodes; j++)
        {
            if (_adjacencyMatrix[v][j] == 1 && _nodes[j].IsVisited == false)
            {
                return j;
            }
        }
        return -1;
    }
}

To call it, just use the code.

var graph = new Graph(adjacenyMatrix, adjacenyMatrix.GetLength(0));
graph.DepthFirstSearch();

Please point it out the flaws of my algorithm.

Base on the comment, there is a solution there, I would like C# code. However it is not completed. It lacks of the method AdjacentNodes(T current).

have a look at this: http://stackoverflow.com/questions/58306/graph-algorithm-to-find-all-connections-between-two-arbitrary-vertices :) — osanger, Jan 11 '16 at 14:12
here is a link to the wiki page https://en.wikipedia.org/wiki/Edge_disjoint_shortest_pair_algorithm — Fafore Tunde, Jan 12 '16 at 14:12

score 0 · Answer 1 · answered Jan 11 '16 at 14:34

The problem is that you mark a node as visited once you touch it and only unset the flag at the end of the algorithm. This means a node can never occur in different paths and your search ends really quick. I recommend that you don't store this information in the node itself but you rather check whether a node is already part of the Stack of nodes in the current path. I think this is what you want to do: You want to prevent that a node occurs twice in a path (avoid cycles) and not that a node is added to any path only once during a search.

Further, I don't see how your DFS function returns anything. It just outputs nodes when they are selected but you never check whether you reached the target node.

You also have to change the way new nodes are selected if you don't use the isVisited flag anymore. I recommend a recursive solution for your DFS. Write a function that takes the current path (Stack) as a parameter, then it determins all adjacent nodes not part of the stack and then it iterates over them by calling itself recursively for each such node (with the respective node added to the stack).

Find all paths from start node to the end node in a graph

1 Answers1