python et le calcul du chemin le plus court
*******************************************

un petit bout de code bien sympathique pour calculer le chemin le plus court entre deux points via une matrice d’évaluation des distances et l’algo de Dijkstra.

En gros on donne une valeur pour la distance entre 2 points (A -> B a une valeur, B -> A en a une autre) Puis on lance le calcul

.. code-block:: python

    # file priodict.py
    # Priority dictionary using binary heaps
    # David Eppstein, UC Irvine, 8 Mar 2002
    # extract on http://code.activestate.com/recipes/117228/
    
    from __future__ import generators
    
    class priorityDictionary(dict):
        def __init__(self):
            '''Initialize priorityDictionary by creating binary heap
            of pairs (value,key).  Note that changing or removing a dict entry will
            not remove the old pair from the heap until it is found by smallest() or
            until the heap is rebuilt.'''
            self.__heap = []
            dict.__init__(self)
    
        def smallest(self):
            '''Find smallest item after removing deleted items from heap.'''
            if len(self) == 0:
                raise IndexError, "smallest of empty priorityDictionary"
            heap = self.__heap
            while heap[0][1] not in self or self[heap[0][1]] != heap[0][0]:
                lastItem = heap.pop()
                insertionPoint = 0
                while 1:
                    smallChild = 2*insertionPoint+1
                    if smallChild+1 < len(heap) and \
                            heap[smallChild] > heap[smallChild+1]:
                        smallChild += 1
                    if smallChild >= len(heap) or lastItem <= heap[smallChild]:
                        heap[insertionPoint] = lastItem
                        break
                    heap[insertionPoint] = heap[smallChild]
                    insertionPoint = smallChild
            return heap[0][1]
    
        def __iter__(self):
            '''Create destructive sorted iterator of priorityDictionary.'''
            def iterfn():
                while len(self) > 0:
                    x = self.smallest()
                    yield x
                    del self[x]
            return iterfn()
    
        def __setitem__(self,key,val):
            '''Change value stored in dictionary and add corresponding
            pair to heap.  Rebuilds the heap if the number of deleted items grows
            too large, to avoid memory leakage.'''
            dict.__setitem__(self,key,val)
            heap = self.__heap
            if len(heap) > 2 * len(self):
                self.__heap = [(v,k) for k,v in self.iteritems()]
                self.__heap.sort()  # builtin sort likely faster than O(n) heapify
            else:
                newPair = (val,key)
                insertionPoint = len(heap)
                heap.append(None)
                while insertionPoint > 0 and \
                        newPair < heap[(insertionPoint-1)//2]:
                    heap[insertionPoint] = heap[(insertionPoint-1)//2]
                    insertionPoint = (insertionPoint-1)//2
                heap[insertionPoint] = newPair
    
        def setdefault(self,key,val):
            '''Reimplement setdefault to call our customized __setitem__.'''
            if key not in self:
                self[key] = val
            return self[key]
    
    # file test.py
    # Dijkstra's algorithm for shortest paths
    # David Eppstein, UC Irvine, 4 April 2002
    # extract on http://code.activestate.com/recipes/119466/
    
    # http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/117228
    from priodict import priorityDictionary
    
    def Dijkstra(G,start,end=None):
                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)
    
    def shortestPath(G,start,end):
        """
        Find a single shortest path from the given start vertex
        to the given end vertex.
        The input has the same conventions as Dijkstra().
        The output is a list of the vertices in order along
        the shortest path.
        """
    
        D,P = Dijkstra(G,start,end)
        Path = []
        while 1:
            Path.append(end)
            if end == start: break
            end = P[end]
        Path.reverse()
        return Path
    
    if __name__ == "__main__":
        #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}, 'w':{}}
        #print shortestPath(G,'s','w')
        G = {'MSK100':{'MPLIE':1, 'MPSFT':1, 'MPCLG':1,'MRE100':1},
            'MPLIE':{'MSK100':1},
            'MPSFT':{'MSK100':1},
            'MPCLG':{'MSK100':1},
            'MRE100':{'MSK100':1, 'MPDSC':1,'MMO100':1, 'MPCLG2':1, 'MPCCP':1, 'MPFCO':1},
            'MPCLG2':{'MRE100':1},
            'MPCCP':{'MRE100':1},
            'MPFCO':{'MRE100':1},
            'MPDSC':{'MRE100':1},
            'MMO100':{'MPCLT':1, 'MPPLA':1},
            'MPCLT':{'MMO100':1},
            'MPPLA':{'MMO100':1}
        }
        print shortestPath(G,'MSK100','MPPLA')