Advanced Graph Theory: Pathfinding, Traversal Algorithms, and Dijkstra's Model

Introduction to Graph Paths and Practical Applications

• The study of graph paths extends beyond identifying immediate neighbors of a node. It focuses on the exploration of the graph to determine reachability and connectivity between disparate locations.
• Real-World Metaphor (New Zealand Transportation Graph):
  • In a hypothetical graph of New Zealand, nodes represent physical locations (e.g., Hamilton, Auckland, Christchurch, Queenstown).
  • Edges represent methods of transportation between these nodes.
  • Example Road Edge: A road connecting Hamilton and Auckland.
  • Example Flight Edge: A plane route connecting Auckland and Christchurch.
• Analytical Questions Solvable via Graph Paths:
  • Identifying how many distinct nodes are reachable when restricted to a specific mode of travel (e.g., only traveling by road).
  • Determining the feasibility of a path between two distant nodes (e.g., Hamilton to Queenstown) under specific constraints (e.g., only using plane travel).
• Path Representation: A path is typically represented as a list of edges. The length of the path is determined by counting the total number of edges required to traverse from the starting node to the target node.

Searching for Path Validity via Depth First Traversal (DFS)

• Mechanism: Depth-first traversal involves exploring as deeply as possible into a graph by recursively visiting adjacent neighbors.
• Process:
  • Start at a specific node.
  • Mark the current node as "visited."
  • Move to an adjacent node recursively until a dead end or a previously visited node is reached.
  • If a dead end is reached, the algorithm backtracks to the previous branch point to continue exploration.
• Applications of DFS:
  • Path Validity: DFS is effective for answering binary questions, such as "Is there a valid path between Node A and Node B?"
  • Cycle Detection: Because the algorithm tracks visited nodes, it can easily identify when a path loops back on itself, indicating a cycle in the graph.
• Efficiency Limitations: DFS is generally inefficient for finding the shortest path. It lacks an inherent strategy for optimization, often moving in a random direction or exploring irrelevant branches of the graph before finding the target.
• Directed Graph Example:
  • In a directed graph, if Node $D$ only has an outgoing arrow (transition) and no incoming arrows, it is impossible to reach Node $D$ from any other node like Node $B$.
  • A DFS starting at Node $B$ might visit Node $A$, then Node $C$, eventually realizing that all adjacent nodes from $C$ are already visited, thereby proving no path to $D$ exists.

Finding Shortest Paths in Unweighted Graphs via Breadth First Traversal (BFS)

• Mechanism: Breadth-first traversal explores the graph in concentric rings or "steps." It evaluates all nodes one step away, then all nodes two steps away, and so on.
• Algorithm for Shortest Path calculation:
  • Initialize all path costs to a default invalid value, such as $-1$, to indicate that the nodes have not yet been visited.
  • Set the starting node's cost to $0$.
  • As each new node is visited, its distance is recorded as the distance of its parent node plus $1$.
• Strengths: BFS is the optimal choice for unweighted graphs because it guarantees that the first time a node is reached, it is via the fewest number of edges possible.
• Weaknesses: It is unsuitable for weighted graphs. A path with fewer edges (which BFS would prioritize) might actually have a much higher total weight than a multi-edge path with lower weight values.

Class Exercise: Adjacency Graph Analysis and Shortest Path Discovery

• Scenario: Determining the shortest path from Node $D$ to Node $G$ based on a provided adjacency list.
• Step-by-Step Algorithm Execution (Starting at Node $D$):
  1. Mark Node $D$ with a distance of $0$.
  2. Identify adjacent nodes: only Node $B$ is adjacent to $D$. Mark Node $B$ with a distance of $1$.
  3. Identify nodes adjacent to $B$: Nodes $A$, $D$, and $E$. Since $D$ is visited, mark $A$ and $E$ with distance $2$.
  4. Evaluate neighbors of $A$ and $E$ to find nodes at distance $3$.
     • Neighbors of $A$ include $B$ (visited) and $C$. Mark $C$ with distance $3$.
     • Neighbors of $E$ include $B$ (visited), $F$, and $H$. Mark $F$ and $H$ with distance $3$.
  5. Evaluate nodes at distance $4$.
     • Neighbors of $C$: Node $A$ (visited), Node $F$ (visited), and Node $G$. Mark $G$ with distance $4$.
• Results: The shortest path identified was distance $4$.
• Redundant Paths Found: Two paths of the same length were identified by students:
  • $D \rightarrow B \rightarrow E \rightarrow F \rightarrow G$
  • $D \rightarrow B \rightarrow A \rightarrow C \rightarrow G$
• Conclusion: Once the target node is found at a specific distance step, the algorithm can stop. This BFS approach also simultaneously finds the shortest path from the start node to every other node in the graph encountered during the search (e.g., distance to $F$ is $3$; distance to $E$ is $2$).

Dijkstra’s Algorithm for Weighted Graphs

• Background: Named after the computer scientist Edsger W. Dijkstra, this is a famous greedy algorithm used to find the shortest path between vertices on a weighted graph.
• The "Greedy" Philosophy: The algorithm makes the best local choice at each step. It always prioritizes the exploration of the node that currently has the lowest cumulative weight from the start.
• Core Constraint: Weights must be strictly positive (non-negative). Negative weights invalidate the greedy assumption because a later "magic" negative number could significantly reduce the cost of a path that previously seemed long, breaking the logic of only exploring the shortest current path.
• Process Illustration (Board Example):
  • Starting at Node $A$ ($weight = 0$).
  • Path to $B$ has a weight of $1$, path to $C$ has weight $2$.
  • Even if a later path from $C$ back to $B$ has a weight, if the total cumulative weight is higher than the known weight of $1$, that path is ignored.
  • The algorithm continues until the target node is reached and no other unexplored paths have a total cumulative weight smaller than the path found.
• Efficiency: Dijkstra's algorithm is efficient because it does not require exploring the entire graph. It only searches outward until it determines there are no other paths with lower costs than the one reaching the target. This makes it viable for large-scale systems like Google Maps.

Implications of Negative Weights in Graphs

• Real-World Scenarios for Weights:
  • Distance or transit time (typically positive).
  • Elevation: Moving down a hill could be modeled as a "negative" effort, though Dijkstra's algorithm cannot handle this if true negative totals are possible.
  • Trading and Finance: A node could represent a person, and an edge could represent a trade. If someone is paid to take a good away, it represents a negative cost/weight.
  • Social Networks: Positive numbers for friendship, negative numbers for enmity. This could lead to complex paths where the "most ambivalent" or "most hostile" path is sought.
• Technical Note: If a graph contains negative weights, Dijkstra's algorithm becomes unreliable, and different pathfinding algorithms (like Bellman-Ford) must be utilized.

Assignment 4: Airport Simulator and Priority Queues

• Overview: The assignment requires creating a simulator for an airport with limited runway resources.
• Core Components:
  • Priority Queue Implementation: Used to manage aircraft landing and takeoff order.
  • Prioritization Logic:
    1. Emergency Status: Planes with declared emergencies receive top priority.
    2. Fuel Levels: Planes with low fuel are prioritized over those with high fuel to prevent mid-air accidents.
    3. Waiting Time: Planes on the ground that have been waiting for a long time are prioritized to ensure throughput.
• Simulation Mechanics:
  • The simulator processes time in blocks (e.g., $1\,hour$ passages).
  • During each cycle, aircraft fuel levels must be decreased.
  • Because fuel levels change, the priority of the plane objects in the queue must be updated. This is achieved using a Heapify function rather than moving planes to a new queue.
• Technical Requirements:
  • JUnit Tests: Students must write their own non-AI generated unit tests for all major functions.
  • CSV Output: The simulator must print the results (e.g., flight landing order) to a $.csv$ file.
  • Constructors: One for generating random planes (for simulation) and one with specific parameters (for testing).
  • Thread.sleep(): Used to slow down the simulation output for visibility.
• Evaluation Criteria: Solution quality is emphasized over "hard coding." The code should be modular and modifiable (e.g., built to easily add features like notifications for planes exploding due to fuel exhaustion).

Questions & Discussion

• Question: Is the "distance" mentioned in the algorithm basically just the biggest cost?

• Answer: In unweighted graphs, yes, the balance is essentially the distance or total edges. In weighted graphs, we refer to the "cost" as the cumulative weight along the edges, while "distance" might technically refer to the number of nodes visited.

• Question: Will the algorithm take a long time to explore if a roundabout route is actually shorter?

• Answer: Yes, if a roundabout route (many edges) has a lower cumulative weight than a direct route (few edges), the algorithm will explore all relevant nodes until it can mathematically guarantee that the shortest path has been found. While it might feel annoying to visit many nodes, the algorithm is designed to minimize the total number of visits required.