Python networkx 模块，single_source_dijkstra() 实例源码

def get_shortest_path_length_with_limit(self, vertex1, vertex2, cutoff=None):
        """
        Parameters
        ----------
        vertex1:
        vertex2:
        cutoff:

        Returns
        -------
        NxGraph: Graph object

        Examples
        --------
        >>>
        """
        try:
            return nx.single_source_dijkstra(self._graph, source=vertex1, target=vertex2, cutoff=cutoff,
                                             weight=self._weight_field)
        except nx.NetworkXNoPath:
            return 0

def getOwnerToOwnerCentrality(self, graph):
        """ compute the network centrality of all the nodes owned by a person
        with respect to all shortest paths beteween any owner"""

        nodeOwner = {}  # node -> owner
        ownerNodes = defaultdict(list)  # owner -> [nodes]
        ownerCentrality = defaultdict(int)
        ownerNodes, nodeOwner = self.get_owner_distribution(graph)
        counter = 0
        shortestPathAndDistance = {}
        for n in graph.nodes():
            shortestPathAndDistance[n] = nx.single_source_dijkstra(graph, n)
            # returns a couple (distance, path)
        for i in range(len(ownerNodes)):
            from_owner, from_nodes = ownerNodes.items()[i]
            for j in range(i+1, len(ownerNodes)):
                to_owner, to_nodes = ownerNodes.items()[j]
                shortest_path = []
                shortest_cost = 0
                for s in from_nodes:
                    for d in to_nodes:
                        if not shortest_path or shortestPathAndDistance[s][0][d] < shortest_cost:
                                shortest_path = shortestPathAndDistance[s][1][d]
                                shortest_cost = shortestPathAndDistance[s][0][d]
                counter += 1
                path_set = set([nodeOwner[node] for node in shortest_path])
                for o in path_set:
                    ownerCentrality[o] += 1
        print "# owner".rjust(long_align_space), ",",\
              "owner-to-owner cent.".rjust(long_align_space)
        for (p, c) in sorted(ownerCentrality.items(), key=lambda x: -x[1]):
            print p.rjust(long_align_space), ",",\
                str(c*1.0/counter).rjust(long_align_space)
        print ""
        print ""
        return ownerCentrality, counter

def policy_buchi_pa(pa, weight_label='weight'):
    '''Computes the policy.'''
    if not pa.final:
        return float('Inf'), None

    vinit = generate_unique_node()
    pa.g.add_node(vinit)
    pa.g.add_edges_from([(vinit, init, {weight_label: 0}) for init in pa.init])

    prefix_costs, prefix_paths = nx.single_source_dijkstra(pa.g, source=vinit,
                                                           weight=weight_label)
    pa.g.remove_node(vinit)

    opt_cost, opt_suffix_path = float('Inf'), None
    for final in pa.final:
        if final in prefix_costs:
            suffix_cost, suffix_path = source_to_target_dijkstra(pa.g,
                    source=final, target=final, degen_paths=False,
                    weight_key=weight_label)
            if prefix_costs[final] + suffix_cost < opt_cost:
                opt_cost = prefix_costs[final] + suffix_cost
                opt_suffix_path = suffix_path

    if opt_suffix_path is None:
        return float('Inf'), None

    opt_final = opt_suffix_path[0]
    return (opt_cost, [u[0] for u in prefix_paths[opt_final][1:]],
            [u[0] for u in opt_suffix_path])