Algorithm-Implementations Show johnson.py Source code
Return
Download Algorithm-Implementations：
download johnson.py Source code
- Download Algorithm-Implementations Source code - Type:.py
- def initialize(G, s):
- """Initialize graph G and vertex s."""
- V, E = G
- d = {v: float('inf') for v in V}
- p = {v: None for v in V}
- d[s] = 0
- return d, p
- def bellman_ford(G, w, s):
- """Bellman-Ford's algorithm for shortest-path search. Expects oriented graph.
- Parameter G is a graph represented as a tuple of vertexes and edges. The
- parametr w represents weights of each edge of the graph G (w: E -> R).
- """
- d, p = initialize(G, s)
- V, E = G
- for _ in range(len(V)-1):
- for (u, v) in E:
- if d[v] > d[u] + w[u, v]:
- d[v] = d[u] + w[u, v]
- p[v] = u
- for (u, v) in E:
- if d[v] > d[u] + w[u, v]:
- raise RuntimeError('Graph contains negative cycles.')
- return d, p
- def dijkstra(G, w, s):
- """Dijkstra's algorithm for shortest-path search."""
- d, p = initialize(G, s)
- V, E = G
- S = set(V)
- while S:
- u = min(S, key=lambda x: d[x])
- S = S - {u}
- for (t, v) in E:
- if t == u and d[v] > d[u] + w[u, v]:
- d[v] = d[u] + w[u, v]
- p[v] = u
- return d, p
- def johnson(G, w):
- """Johnson's algorithm for shortest-path search between all vertexes of
- the graph G. G is represented with an adjacancy list. The parameter w
- represents weights of edges.
- """
- V, E = G
- G_ = (V + ['S'], E + [('S', v) for v in V])
- V_, E_ = G_
- w_ = dict(w.items() + [((u, v), 0) for (u, v) in E_ if u == 'S'])
- d, p = bellman_ford(G_, w_, 'S')
- h = {}
- for v in V:
- h[v] = d[v]
- w__ = {}
- for (u, v) in E:
- w__[u, v] = w[u, v] + h[u] - h[v]
- D = {(u, v): None for u in V for v in V}
- for u in V:
- d_, p_ = dijkstra(G, w__, u)
- for v in V:
- D[u, v] = d_[v] + h[v] - h[u]
- return D
- if __name__ == '__main__':
- V = ['A', 'B', 'C', 'D'] # vertexes
- E = [('A', 'B'), ('B', 'C'), ('C', 'D'), ('D', 'B')] # edges
- w = {('A', 'B'): 1, ('B', 'C'): 3, ('B', 'D'): 1,
- ('C', 'D'): 8, ('D', 'B'): -2} # weights
- print johnson((V, E), w)
downloadjohnson.py Source code
- Download Algorithm-Implementations Source code
Related Source Codes/Software：
raty - 2017-04-22
RDVTabBarController - Highly customizable tabBar and tabBarController fo... 2017-04-22
material-icon-lib - Library containing over 1500 material vector icons... 2017-04-21
httpdiff - Perform the same request against two HTTP servers ... 2017-04-21
jquerytools - The missing UI library for the Web
... 2017-04-21
mcrouter - Mcrouter is a memcached protocol router for scalin... 2017-04-22
dynomite - A generic dynamo implementation for different k-v ... 2017-04-22
kityminder - Baidu brain figure 2017-04-22
llvm - Mirror of official llvm git repository located at ... 2017-04-22
RBBAnimation - Block-based animations made easy, comes with easin... 2017-04-22
ied - 2017-04-29
Nimble - A Matcher Framework for Swift and Objective-C 2017-04-29
MHVideoPhotoGallery - A Photo and Video Gallery 2017-04-29
shoulda-matchers - Collection of testing matchers extracted from Shou... 2017-04-29
Android-SlideExpandableListView - A better ExpandableListView, with animated expanda... 2017-04-29
AppSales-Mobile - App Sales allows iPhone and Mac App Store develope... 2017-04-29
react-templates - Light weight templates for react
... 2017-04-28
afterglow-theme - A minimal dark Theme for Sublime Text 2 and 3 2017-04-28
jwt-go - Golang implementation of JSON Web Tokens (JWT) 2017-04-28
DeerResume - Tool MarkDown online resume, online preview, edit,... 2017-04-28