Python Algorithm: Pt. 10 Bellman Ford
Me: “Hello Mr. Ford, can you tell us about yourself?”
Bellman Ford: “Sure. I am a python algorithm who finds the shortest route to a certain destination, much like Dijkstra.”
Me: “Alright then. To the Medium viewers here: Bellman Ford is NOT a person. It does sound like someone’s name, but no. It actually, like what Mr. Ford here said earlier, is an algorithm used to try to identify the closest and most efficient way to get from point A to point B. Check out Dijkstra’s post here: https://chekailiang.medium.com/python-algorithm-pt-9-dijkstra-ea23635be325.”
Bellman Ford: “Indeed. I suppose the explanation of Dijkstra would suffice. The distance between different points are combined and calculated to form a matrix of different points connected to each other, with the distance between them written on the line between, and using the algorithm to search every possible sum of the distance combined and at the same time checking each of them and comparing them. The smallest sum of the distance is the nearest, hence completing the algorithm’s task and, depending on the user’s wish, outputting it in the terminal. However…”
Me: “Allow me, Mr. Ford. There is one difference between Bellman and Dijkstra, and one only: Mr. Ford here is pretty negative all the time. Literally. Bellman is used for the same purpose as Dijkstra, but for calculating negative numbers.”
Bellman Ford: “I suppose an example will be in order.”
def get_edges(graph):n1 = []n2 = []weight = []for i in graph:for j in graph [i]:if graph[i][j] != 0:weight.append(graph[i][j])n1.append(i)n2.append(j)return n1, n2, weightdef bellman_ford(graph, start):n1, n2, weight = get_edges(graph)nodes = dict((i, INF) for i in graph)nodes[start] = 0for times in range(len(graph) - 1):cycle = 0for i in range (len(weight)):new_cost = nodes[n1[i]] + weight[i]if new_cost < nodes[n2[i]]:nodes[n2[i]] = new_costcycle = 1if cycle == 0:breakflag = 0for i in range(len(nodes)):if nodes[n1[i]] + weight[i] < nodes[n2[i]]:flag = 1breakif flag:return 'negative cycle'return nodesINF = 999graph = {'A':{'A':0, 'B':2, 'C':4},'B':{'B':0, 'C':7, 'E':6},'C':{'C':0, 'D':6, 'E':2},'D':{'D':0, 'E':8, 'G':4},'E':{'E':0, 'G':2},'G':{'G':0}}rtn = bellman_ford(graph, 'A')print(rtn)
Me: “Thank you Mr. Ford, for joining us today at Algorithm interviews for dummies.”
Bellman Ford: “No problem. And if you, viewer, enjoy our posts, remember to clap for us. Thank you.”
Me & Bellman Ford: “Until next time!”