Cfrgtkky

I have a graph as below:

I store it in the dictionary data structure.
Suppose I want to find path from D to M:

Then I want something like find shortest path from D to M :

D-H-K-M

and then take it's parent nodes where it finds path from A-M without D in it,

A-E-I-L-M

and B-M without D in it,

B-E-I-L-M

For now, I have been able to find just the shortest path from D-M.

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 == None:

            graph_dict = {}

        self.__graph_dict = graph_dict



    def vertices(self):

        """ returns the vertices of a graph """

        return list(self.__graph_dict.keys())



    def edges(self):

        """ returns the edges of a graph """

        return self.__generate_edges()



    def add_vertex(self, vertex):

        """ If the vertex "vertex" is not in

            self.__graph_dict, a key "vertex" with an empty

            list as a value is added to the dictionary.

            Otherwise nothing has to be done.

        """

        if vertex not in self.__graph_dict:

            self.__graph_dict[vertex] = 



    def add_edge(self, edge):

        """ assumes that edge is of type set, tuple or list;

            between two vertices can be multiple edges!

        """

        edge = set(edge)

        (vertex1, vertex2) = tuple(edge)

        if vertex1 in self.__graph_dict:

            self.__graph_dict[vertex1].append(vertex2)

        else:

            self.__graph_dict[vertex1] = [vertex2]



    def __generate_edges(self):

        """ A static method generating the edges of the

            graph "graph". Edges are represented as sets

            with one (a loop back to the vertex) or two

            vertices

        """

        edges = 

        for vertex in self.__graph_dict:

            for neighbour in self.__graph_dict[vertex]:

                if {neighbour, vertex} not in edges:

                    edges.append({vertex, neighbour})

        return edges



    def __str__(self):

        res = "vertices: "

    for k in self.__graph_dict:

        res += str(k) + " "

        res += "nedges: "

        for edge in self.__generate_edges():

            res += str(edge) + " "

        return res



    def find_path(self, start_vertex, end_vertex, path=):

        """ find all paths 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 

        paths = 

        for vertex in graph[start_vertex]:

            if vertex not in path:

                extended_paths = self.find_path(vertex,

                                                 end_vertex,

                                                 path)

                for p in extended_paths:

                    paths.append(p)

        return paths





graph_dict = { 'a' : ['d', 'e'],

      'b' : ['d', 'e'],

      'c' : ['h'],

      'd' : ['a', 'b', 'h'],

      'e' : ['a', 'b', 'i'],

      'f' : ['i'],

      'g' : ['k'],

      'h' : ['c', 'd', 'k'],

      'i' : ['e', 'f', 'l'],

      'j' : ['l'],

      'k' : ['g', 'h', 'm'],

      'l' : ['i', 'j', 'm'],

      'm' : ['k', 'l']

    }



graph = Graph(graph_dict)





print('The path from vertex "d" to vertex "m":')

path = graph.find_path('d', 'm')

min = len(path[0])

for path_list in path:

    if len(path_list)<min:

        min = path_list

print(min)

Thank you!