Shortest Path Algorithms

• Study notes generated from the provided text.

Overview

• Focus is on shortest paths in graphs.

Shortest Paths

• Given a weighted graph G = (V, E, w) with two specific nodes, the goal is to find the shortest path P from node s to node t.
• The total weight of path P is minimized.
• Hnodes are cities, edges are roads, and weights are travel times.

General Problem: Single Source Shortest Path (SSSP)

• Many algorithms finding the shortest path between two nodes solve a more general problem.
• It finds the shortest path from the starting node s to all other nodes in the network.
• Solution usually involves constructing a tree of shortest paths rooted at s.

Properties of Shortest Paths

• If the shortest paths are unique, they form a tree.
• Every subpath of a shortest path is also a shortest path.
• Even with multiple shortest paths, a single path to each node can be chosen to form a tree

Shortest Path Tree vs. Minimum Spanning Tree

• Two distinct types of trees.
• Shortest path trees are rooted and directed.
• Minimum spanning trees are undirected and unrooted.
• Shortest path trees are more suitable for directed graphs
• Minimum spanning trees are better for undirected graphs.
• Unique edge weights ensure a single minimum spanning tree, but multiple shortest path trees may exist depending on the starting node.
• Shortest path trees may use different edges than the minimum spanning tree.

Negative Weights

• Shortest path problems typically assume positive edge weights.
• However, negative weights can be useful.

Negative Cycles

• Can cause issues in shortest path problems, potentially leading to undefined shortest paths.
• The shortest path from s to t exists if there's a path and no path from s to t intersects a negative cycle.
• If a path touches a negative cycle, a shorter path exists by traversing the cycle one more time.
• These cases technically involve finding shortest walks, not shortest paths.
• If a shortest walk exists it must be a simple path.
• Finding the simple shortest path when negative cycles exist is NP-hard

Negative Weight Notes and Undirected Graphs

• The focus may be on directed graphs when negative weights are involved.
• Some algorithms can work on undirected graphs with modifications if negative weights are not allowed.

Handling Negative Weights

• Handling negative weights in undirected graphs is more complex
• Replacing an undirected edge with negative weight creates a negative cycle and requires some additional work.
• Hedges that contain negative weights may no longer be the shortest path

Non-negative Edges

• The set of all the shortest path cannot create a tree

Undirected and Negative Weights

• Course work does not cover undirected nets with negative weights
• The simplest way to find the shortest path in undirected nets with negative weight, is to do a transformation.
• The transformation has a time complexity of O(VE + V * V log V)
• The process builds on transfers of maximum weighted matching

Single Source Shortest Path Algorithms

• (SSSP) algorithms described
• Many SSSP algorithms can be seen as specific versions of one general algorithm.
• The general algorithm was first suggested my Lester Ford in 1956
• The algorithm was published independently by George Dantzig in 1957 and George Minty in 1958

SSSP algorithm node values

• Each node v stores two values related to tentative path s ~ v
• dist(v) is the length of the tentative path s ~ v, or infinite if no such path exists
• pred(v) is the parent of v on the path s ~ v, or Null if no parent exists

Initialize SSSP algorithm

• Node distances and parents are initialized as shown

Spanning Edges are relaxed

• An edge u -> v is relaxed is dist(u) + w(u -> v) < dist(v)

Tentative path assumptions

• If u -> v is relaxed then the tentative path s ~ v is wrong, because s ~ u -> v is shorter

Repairing tentative paths

• repair or lower the cost, by relaxing the nodes
• An edge u -> v that is tense is relaxed until there are no more tense edges left

Correctness of Ford SSSP Algorithm, it can be shown that:

• The parent pointers define a correct shortest-path tree
• Each value dist(v) is the true distance of its shortest path from s to v.
• If s can't reach v, dist(v) = infinity.
• If a negative cycle can be reached from s, the algorithm never stops.

Ford Algorithm Proofs

• The Ford algorithm is proved through the affirmational statements that hold true:
  • For any time in the algorithms iteration, dist(v) is either infinite, or the length from s to v
  • If the net has no negative circles, the dist(v) is either infinite or the length of the line from s to v
  • If there are not negative circles, then dist(v) is in relation to length between s and v
  • All nodes in G do not have spenntur then dist(v)

Ford Algorithm Implementations

• The implementations can alter based on different types of nets

Breadth-First Search (BFS)

• A type of Ford Algorithm
• Used for unweighted nets

Breadth-First Search

• Uses a queue (FIFO) to hold nodes.
• Initially, the queue contains only the starting node s.
• Each vertex u is taken from the queue.
• Slacks the line u -> v, and v is added to the queue
• Once the queue is empty, returns to start

Breadth-First Search Phase Tracking

• Make it easier to follow processes by adding phases.
• Phases can be tracked in the queue.
• The algorithm adds a phase to the queue and then goes through the nodes.
• Phases begin and return during the marking of the queue.
• The first phase starts by queuing the starting node
• Phases are ignored, only really used to mark the queue.
• Gives a more accurate timeline and process flow.

Important Facts about BFS with distance (v)

• BFS gives the distances in a non-decreasing order; the distances never increase.
• The line dist(v) = dist(u) + 1 runs only once during each node visit.
• pred(v) can be the distance in a path dist(v) and can then get checked.
• The line dist(v) > dist(u) comes from the distances given from dist(u) + 1

When BFS Ends

• BFS ends when path dist(v) is the smallest G can make it from vertex s -> v.
• Distance (v) and the distance it creates helps identify the smallest distance it has.