def dijkstra(self, start, end=None):
        """
            Find shortest paths from the start vertex to all
            vertices nearer than or equal to the end.

            The input graph G is assumed to have the following
            representation: A vertex can be any object that can
            be used as an index into a dictionary.  G is a
            dictionary, indexed by vertices.  For any vertex v,
            G[v] is itself a dictionary, indexed by the neighbors
            of v.  For any edge v->w, G[v][w] is the length of
            the edge.  This is related to the representation in
            <http://www.python.org/doc/essays/graphs.html>

            Of course, G and G[v] need not be Python dict objects;
            they can be any other object that obeys dict protocol,
            for instance a wrapper in which vertices are URLs
            and a call to G[v] loads the web page and finds its links.

            The output is a pair (D,P) where D[v] is the distance
            from start to v and P[v] is the predecessor of v along
            the shortest path from s to v.

            Dijkstra's algorithm is only guaranteed to work correctly
            when all edge lengths are positive. This code does not
            verify this property for all edges (only the edges seen
             before the end vertex is reached), but will correctly
            compute shortest paths even for some graphs with negative
            edges, and will raise an exception if it discovers that
            a negative edge has caused it to make a mistake.

            Introduction to Algorithms, 1st edition), page 528:

            G = { 's':{'u':10, 'x':5},
                 ' u':{'v':1, 'x':2},
                 'v':{'y':4},
                 'x':{'u':3, 'v':9, 'y':2},
                 'y':{'s':7, 'v':6}
            }
        """
        G = self.adj()

        D = {}    # dictionary of final distances
        P = {}    # dictionary of predecessors
        Q = priorityDictionary()   # est.dist. of non-final vert.
        Q[start] = 0

        for v in Q:
            D[v] = Q[v]
            if v == end: break

            for w in G[v]:
                vwLength = D[v] + G[v][w]
                if w in D:
                    if vwLength < D[w]:
                        raise (ValueError, "Dijkstra: found better path to already-final vertex")
                elif w not in Q or vwLength < Q[w]:
                    Q[w] = vwLength
                    P[w] = v

        return D,P

            Find shortest paths from the start vertex to all
            vertices nearer than or equal to the end.

            The input graph G is assumed to have the following
            representation: A vertex can be any object that can
            be used as an index into a dictionary.  G is a
            dictionary, indexed by vertices.  For any vertex v,
            G[v] is itself a dictionary, indexed by the neighbors
            of v.  For any edge v->w, G[v][w] is the length of
            the edge.  This is related to the representation in
            <http://www.python.org/doc/essays/graphs.html>

            Of course, G and G[v] need not be Python dict objects;
            they can be any other object that obeys dict protocol,
            for instance a wrapper in which vertices are URLs
            and a call to G[v] loads the web page and finds its links.

            The output is a pair (D,P) where D[v] is the distance
            from start to v and P[v] is the predecessor of v along
            the shortest path from s to v.

            Dijkstra's algorithm is only guaranteed to work correctly
            when all edge lengths are positive. This code does not
            verify this property for all edges (only the edges seen
             before the end vertex is reached), but will correctly
            compute shortest paths even for some graphs with negative
            edges, and will raise an exception if it discovers that
            a negative edge has caused it to make a mistake.

            Introduction to Algorithms, 1st edition), page 528:

            G = { 's':{'u':10, 'x':5},
                 ' u':{'v':1, 'x':2},
                 'v':{'y':4},
                 'x':{'u':3, 'v':9, 'y':2},
                 'y':{'s':7, 'v':6}
            }
        
recipes/Python/579141_Simple_Graph_library/recipe-579141.py