CODEWITHSUNDEEP
pythongraphpathtraversaledge-list
Hsin
Hsin

Reputation: 317

Why graph doesn't find correct path?

I've tried to create graph with the help of the following link but when I used find_path method I got incorrect path returned. Link:

http://www.python-course.eu/graphs_python.php

Code:

class Graph(object):
    def __init__(self, graph_dict=None):
        """ initializes a graph object
            If no dictionary or None is given, an empty dictionary will be used
        """
        if graph_dict is None:
            graph_dict = {}
        self.__graph_dict = graph_dict

    def find_path(self, start_vertex, end_vertex, path=[]):
        """ find a path from start_vertex to end_vertex
            in graph """
        graph = self.__graph_dict
        path = path + [start_vertex]
        if start_vertex == end_vertex:
            return path
        if start_vertex not in graph:
            return None
        for vertex in graph[start_vertex]:
            if vertex not in path:
                extended_path = self.find_path(vertex,
                                               end_vertex,
                                               path)
                if extended_path:
                    return extended_path
        return None

g = {"a": ["c", "d"],
     "b": ["a", "c"],
     "c": ["a", "b", "c", "d", "e"],
     "d": ["c", "e"],
     "e": ["c", "f"],
     "f": ["c"]
     }

graph = Graph(g)

"""
graph:

a<----b         <-- one way
|\   /          --- two way
| \ /
|  c <-- f
| / \    ^
v/   \   |
d---->e--/

"""
print graph.find_path("b", "f")

Output: ['b', 'a', 'c', 'd', 'e', 'f']
Should be: ['b', 'a', 'd', 'e', 'f']

What is wrong with find_path method in Graph class?

Upvotes: 0

Views: 65

Answers (2)

Chirag
Chirag

Reputation: 446

Your code is finding the path by following the first node in each node's adjacency list that does not already belong in the graph. It starts at 'b' and then goes to the first node in the adjacency list (['a', 'c']) node 'a'. Then it goes from 'a' to 'c'. Once it is at 'c', it sees that 'a', 'b', and 'c' are already in the path so it goes to 'd'. If you changed the order of your adjacency list in the graph to this, it will print out the order your looking for:

g = {"a": ["d", "c"],
     "b": ["a", "c"],
     "c": ["a", "b", "c", "d", "e"],
     "d": ["e", "c"],
     "e": ["f", "c"],
     "f": ["c"]
     }

Alternatively, you can implement a shortest path algorithm such as Djikstra's to find the shortest path through a graph.

Upvotes: 2

Prune
Prune

Reputation: 77857

You programmed this to find any acyclic path, and return the first one it finds. The path it found is perfectly reasonable; it's simply not the least number of steps.

To find the shortest path, you need to implement either a breadth-first search, or a depth-first search with memoization (keep track of the best known path to each node). Dijkstra's algorithm is good for the shortest path.

Upvotes: 1

Related Questions