shortest_path.theory.txt

                                  ┏━━━━━━━━━━━━━━━━━━━┓
                                  ┃   SHORTEST PATH   ┃
                                  ┗━━━━━━━━━━━━━━━━━━━┛

SHORTEST PATH ALGORITHM ==>       #Finding shortest path between two vertices in a graph
                                  #Can be:
                                  #  - "single-pair": between two given vertices
                                  #  - "single-source": from a given vertex to any vertex
                                  #  - "single-destination": from any vertex to a given vertex
                                  #  - "all-pairs": from any vertex to any vertex
                                  #If there are negative cycles, there is no shortest path.

DJIKSTRA'S ALGORITHM ==>          #Single-source shortest path algorithm.
                                  #Incrementally add closest neighbor vertices.
                                  #Steps:
                                  #  - set current_node to node:
                                  #     - with minimal weight (initially source)
                                  #     - not visited yet
                                  #  - calculate distance from current_node to its neighbors not visited yet
                                  #     - neighbor's weight = distance + current_node's weight,
                                  #       unless neighbor's weight is smaller
                                  #        - initial weight is 0 for source, Infinity for others
                                  #  - repeat
                                  #Best implemented with a min-priority queue:
                                  #  - where weight is the priority
                                  #  - when using a Fibonacci heap, time complexity is O(order*log(order) + size)

BELLMAN-FORD ALGORITHM ==>        #Single-source shortest path algorithm.
                                  #Slower than djikstra's algorithm but can handle negative weights.
                                  #Can also be used to detect negative cycles.