BVB Source Codes

Algorithm-Implementations Show bellmanford.py Source code

Return Download Algorithm-Implementations: download bellmanford.py Source code - Download Algorithm-Implementations Source code - Type:.py
  1. def initialize(G, s):
  2.     """Initialize graph G and vertex s."""
  3.     V, E = G
  4.     d = {v: float('inf') for v in V}
  5.     p = {v: None for v in V}
  6.     d[s] = 0
  7.     return d, p
  8.  
  9.  
  10. def bellman_ford(G, w, s):
  11.     """Bellman-Ford's algorithm for shortest-path search. Expects oriented graph.
  12.    Parameter G is a graph represented as a tuple of vertexes and edges. The
  13.    parametr w represents weights of each edge of the graph G (w: E -> R).
  14.    """
  15.     d, p = initialize(G, s)
  16.     V, E = G
  17.     for _ in range(len(V)-1):
  18.         for (u, v) in E:
  19.             if d[v] > d[u] + w[u, v]:
  20.                 d[v] = d[u] + w[u, v]
  21.                 p[v] = u
  22.     for (u, v) in E:
  23.         if d[v] > d[u] + w[u, v]:
  24.             raise RuntimeError('Graph contains negative cycles.')
  25.     return d, p  # return distances and a tree representing shortest paths
  26.  
  27.  
  28. if __name__ == '__main__':
  29.     V = ['A', 'B', 'C', 'D']  # vertexes
  30.     E = [('A', 'B'), ('B', 'C'), ('C', 'D'), ('D', 'B')]  # edges
  31.     w = {('A', 'B'): 1, ('B', 'C'): 3, ('B', 'D'): 1,
  32.          ('C', 'D'): 8, ('D', 'B'): -2}  # weights
  33.     print bellman_ford((V, E), w, 'A')
  34.  
downloadbellmanford.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

 Back to top