<jupyter_start><jupyter_text>Dynamic Programming in Graphs Bellman-FordAlgorithm for shortest path from single source<jupyter_code>import math

def bellmanFord(G, s):
    n = len(G)
    dist = [math.inf]*n
    path = [None]*n

    dist[s] = 0

    for i in range(n-1):

        for u in range(n):
            for v, w in G[u]:
                f = dist[u] + w
                if f < dist[v]:
                    dist[v] = f
                    path[v] = u

    for u in range(n):
        for v, w in G[u]:
            if dist[v] > dist[u] + w:
                return False, _, _
    
    return True, path, dist
    
import graphviz as gv

def drawAdjListGraph(G):
    dot = gv.Digraph(strict=True)
    n = len(G)
    for u in range(n):
        for v, w in G[u]:
            dot.edge(str(u), str(v), label=str(w))
    
    dot.graph_attr['rankdir'] = 'LR'
    return dot
def loadAdjListGraph(filename):
    G = []
    with open(filename) as file:
        for line in file:
            if line == '*':
                G.append([])
            else:
                temp = line.strip().split(' ')
                temp = [p.split(',') for p in temp]
                temp = [(int(x), int(y)) for x, y in temp]
                G.append(temp)

    return G
%%writefile grafo.al
1,10 2,20
3,50 4,10
3,20 4,33
4,-20 5,-2
5,1
*
G = loadAdjListGraph('grafo.al')
for l in G:
    print(l)
drawAdjListGraph(G)
def draw(path, dist):
    dot = gv.Digraph(comment="G")
    n = len(path)
    for i in range(n):
        dot.node(str(i), str(i))
    for i in range(n):
        if path[i] != None:
            dot.edge(str(path[i]), str(i), label=str(dist[i]))
    dot.graph_attr['rankdir'] = 'LR'
    return dot
ok, path, dist = bellmanFord(G, 0)
print(path)
print(dist)
draw(path, dist)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.14524207011686144, 'fraction_numerical': 0.015581524763494713, 'mean_word_length': 1.8630573248407643, 'pattern_counts': {'":': 0, '<': 6, '<?xml version=': 0, '>': 6, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '174250', 'license': 'CC0-1.0', 'n_tokens_mistral': 691, 'n_tokens_neox': 655, 'n_words': 180, 'path': 'week12/12_Bellman_Ford.ipynb', 'repo_name': 'pcsilcan/aed', 'size': '1797'}