<jupyter_start><jupyter_text>Dijkstra's algorithm:Reference: [Dijkstra's algorithm, Wikipedia, the free encyclopedia](https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm)- Author: <NAME> [\[e-mail\]](mailto:'Israel%20Oliveira%20')<jupyter_code>%load_ext watermark
# Run this cell before close.
%watermark
%watermark --iversion
%watermark -b -r -g
from random import randint
import string

# Only to show the graph:
import networkx as nx
import matplotlib.pyplot as plt<jupyter_output><empty_output><jupyter_text>Simple class for (undirected) graphs:<jupyter_code>class Graph:
    def __init__(self):
        self.nodes = set()
        self.edges = {}
        self.distances = {}

    def add_node(self, value):
        self.nodes.add(value)
        self.edges[value] = []
        
    def add_edge(self, from_node, to_node, distance):
        self.edges[from_node].append(to_node)
        self.edges[from_node] = list(set(self.edges[from_node]))
        self.edges[to_node].append(from_node)
        self.edges[to_node] = list(set(self.edges[to_node]))
        self.distances[tuple(sorted((from_node, to_node)))] = distance
    
    def distance(self, from_node, to_node):
        '''
            Considering only a undirected graph.
        '''
        try:
            return self.distances[tuple(sorted((from_node, to_node)))] if from_node != to_node else 0
        except:
            return float('inf')

    def path_distance(self,nodes):
        return sum([self.distance(nodes[i],nodes[i+1]) for i in range(0,len(nodes)-1)])<jupyter_output><empty_output><jupyter_text>Dijkstra algorithm for computing all shortest path from start node:<jupyter_code>def dijkstra(graph: Graph, node_start: str):
    dist = {node: float('Inf') for node in graph.nodes}
    dist[node_start] = 0
    pi = {}
    Q = list(graph.nodes)
    
    while Q:
        for current_node,_ in sorted(dist.items(), key=lambda x: x[1]):
            if current_node in Q:
                Q.remove(current_node)
                break
        for neighbor in G.edges[current_node]:
            if dist[neighbor] > dist[current_node]+G.distance(neighbor,current_node):
                dist[neighbor] = dist[current_node]+G.distance(neighbor,current_node)
                pi[neighbor] = current_node
    return pi, dist<jupyter_output><empty_output><jupyter_text>For get a path for a given start and end nodes:<jupyter_code>def dijkstra_shortest_path(graph: Graph, node_start: str, node_end: str):
    ver, dist = dijkstra(G,nodes[0])
    if dist[node_end] == float('Inf'):
        print('There is no way to the end node from start node.')
        return None
    shortest_path = [node_end]
    current_node = node_end
    while current_node != node_start:
        shortest_path.append(ver[current_node])
        current_node = ver[current_node]
    return shortest_path[::-1], dist[node_end]<jupyter_output><empty_output><jupyter_text>Generating a well balanced graph (not with much edges).<jupyter_code>?randint
G = Graph()
Gnx = nx.Graph()
nodes = [c for c in string.ascii_uppercase][:10]
for node in nodes:
    G.add_node(node)
for nodefrom in nodes:
    for nodeto in nodes:
        if nodeto != nodefrom:
            n = randint(-400,100)
            if (n >0) and (tuple(sorted((nodefrom, nodeto))) not in G.distances.keys()):
                G.add_edge(nodefrom, nodeto, n)
                Gnx.add_edge(nodefrom, nodeto, distance=n)
n = 8
plt.figure(figsize=(n,n))
pos = nx.circular_layout(Gnx)
labels = nx.get_edge_attributes(Gnx,'distance')
nx.draw(Gnx, pos, with_labels=True)
nx.draw_networkx_edge_labels(Gnx, pos, edge_labels=labels)<jupyter_output><empty_output><jupyter_text>From A<jupyter_code>ver, dist = dijkstra(G,'A')
dist<jupyter_output><empty_output><jupyter_text>to 'E'<jupyter_code>G.path_distance(['A','D'])
dijkstra_shortest_path(G,'A','D')<jupyter_output><empty_output><jupyter_text>Using the NetworkX method:<jupyter_code>print(nx.shortest_path(Gnx,source='A',target='D',weight='distance'))<jupyter_output>['A', 'E', 'J', 'G', 'D']
{'fraction_non_alphanumeric': 0.13108242303872888, 'fraction_numerical': 0.005958291956305859, 'mean_word_length': 3.825149700598802, 'pattern_counts': {'":': 0, '<': 33, '<?xml version=': 0, '>': 35, 'https://': 1, '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': '8', 'dir': 'jupyter-structured-clean-dedup', 'id': '46345', 'license': 'BSD-3-Clause', 'n_tokens_mistral': 1414, 'n_tokens_neox': 1390, 'n_words': 281, 'path': 'dijkstra_alg/Dijkstra.ipynb', 'repo_name': 'ysraell/examples', 'size': '4037'}