The Shortest Path Problem

Introduction

This lecture introduces the Shortest Path Problem (SPP), a fundamental problem in combinatorial optimization. We will explore different facets of this problem, from its definition and real-world applications to its computational complexity and solution approaches. We will discuss the distinction between single-source and all-pairs shortest paths, the concept of optimality, graph representations, and the impact of negative edge costs and cycles. The lecture will also touch upon the NP-hardness of the general SPP and conditions under which polynomial-time solutions are possible. Finally, we will delve into an Integer Linear Programming (ILP) formulation for the SPP and discuss the necessity of subtour elimination constraints.

The Shortest Path Problem

Problem Definition

Finding Optimal Paths in a Graph

The Shortest Path Problem aims to find a path between two nodes in a graph such that the sum of the weights of the edges on the path is minimized. This path is considered "optimal" based on a defined cost metric.

Single-Source vs. All-Pairs Shortest Paths

We can differentiate between two main variants of the problem:

• Single-Source Shortest Path (SSSP): Finding the shortest paths from a single source node to all other nodes in the graph, or to a specific destination node.

• All-Pairs Shortest Path (APSP): Finding the shortest paths between all pairs of nodes in the graph.

Real-World Applications

Navigation Systems (GPS)

A prominent application of the shortest path problem is in navigation systems, such as GPS in cars. These systems need to calculate the optimal route from a starting point to a destination.

Defining Optimality

The concept of an "optimal" path can be defined in various ways depending on the context:

Minimizing Distance (Shortest Path in Kilometers)

Optimality can refer to minimizing the total distance traveled; for example, finding the route with the fewest kilometers. This is the most literal interpretation of "shortest path".

Minimizing Travel Time (Fastest Path)

Alternatively, optimality might mean minimizing the total travel time. In this case, a slightly longer route might be preferred if it involves faster roads like highways, leading to a quicker arrival.

Minimizing Costs (e.g., Tolls, Fuel Consumption)

Optimality can also be defined in terms of minimizing costs, such as tolls, fuel consumption, or other expenses associated with travel. The "cost" can be a generalized measure that combines various factors.

Graph Representation

Nodes (Vertices) and Edges (Arcs)

The underlying structure for the Shortest Path Problem is a graph, which consists of:

• Nodes (or vertices): Represent locations, intersections, or points in a network.

• Edges (or arcs): Represent connections or routes between nodes, such as roads or paths.

Edge Costs (Weights or Lengths)

Each edge in the graph is associated with a cost, weight, or length, representing the "cost" of traversing that connection. As discussed earlier, this cost can represent distance, time, monetary expense, or other relevant metrics. We denote the cost of an edge from node \(i\) to node \(j\) as \(C_{ij}\).

Directed vs. Undirected Graphs

Transforming Undirected Graphs to Directed Graphs (Duplicating Edges)

Graphs can be either directed or undirected. For the Shortest Path Problem, it is often more convenient to work with directed graphs. An undirected graph can be transformed into a directed graph by replacing each undirected edge between nodes \(I\) and \(J\) with two directed arcs: one from \(I\) to \(J\) and another from \(J\) to \(I\). Both directed arcs inherit the cost of the original undirected edge.

Advantages of Directed Graphs (Modeling One-Way Streets, etc.)

Directed graphs are advantageous because they can model real-world scenarios more accurately, such as one-way streets or routes with direction-dependent costs. In a directed graph, travel is only permitted in the direction of the arcs.

Non-Negative vs. Negative Edge Costs

Typical Scenarios with Non-Negative Costs (Distances, Times)

In many practical applications, edge costs are non-negative. For instance, distances and travel times are always positive or zero.

Negative Costs as Profit or Gain (e.g., Revenue)

However, in some scenarios, edge costs can be negative. A negative cost can represent a profit, gain, or revenue obtained by traversing that edge. For example, in logistics, a negative cost might represent a subsidy or a profit from delivering goods along a particular route.

Mixed Cost Scenarios (Both Positive and Negative Costs)

It is possible to have graphs with a mix of both positive and negative edge costs. This can model complex situations where some paths incur costs while others generate profit.

Paths in a Graph

Definition as a Sequence of Vertices (Nodes)

A path in a graph is defined as a sequence of vertices \(V_0, V_1, V_2, \ldots, V_k\) such that for each \(i\) from 0 to \(k-1\), there exists a directed edge from \(V_i\) to \(V_{i+1}\) in the graph. \(V_0\) is the starting node and \(V_k\) is the ending node of the path.

Path Length (Sum of Edge Costs along the Path)

The length or cost of a path \(P = (V_0, V_1, \ldots, V_k)\) is the sum of the costs of the edges in the path: \[\text{Length}(P) = \sum_{i=0}^{k-1} C_{V_i, V_{i+1}}\] where \(C_{V_i, V_{i+1}}\) is the cost of the edge from vertex \(V_i\) to \(V_{i+1}\). A path with \(k+1\) vertices contains \(k\) edges.

The Shortest Path Problem (SPP)

Finding Minimum Cost Paths between Nodes

The Shortest Path Problem (SPP) is to find a path between two specified nodes (a source and a destination) such that the total path length is minimized.

Single-Pair vs. All-Pairs Shortest Paths

Similar to the problem definition, we can consider:

• Single-Pair Shortest Path: Finding the shortest path between a specific pair of source and destination nodes.

• All-Pairs Shortest Path: Finding the shortest paths between all possible pairs of nodes in the graph.

Simple vs. Elementary Paths

Simple Paths (No Repeated Edges/Arcs)

A simple path is a path that does not repeat any edges (arcs).

Elementary Paths (No Repeated Vertices/Nodes)

An elementary path is a path that does not repeat any vertices (nodes). Every elementary path is also a simple path, but the converse is not necessarily true.

Examples Illustrating Different Path Types

Consider a graph. Let’s illustrate path types with an example based on the transcribed lecture’s graph example (though it was for MST, we can adapt it for path examples). Assume edge costs are as given in the transcription example.

• Elementary Path: \(1 \rightarrow 2 \rightarrow 6 \rightarrow 8\). Vertices are \(\{1, 2, 6, 8\}\), no repetition. Cost = \(10 + 1 + 3 = 14\).

• Simple Path (not elementary): It’s difficult to construct a simple path that’s not elementary in this example without more graph details. In general, consider a graph with edges \((A,B), (B,C), (C,B), (B,D)\). Path \(A \rightarrow B \rightarrow C \rightarrow B \rightarrow D\) is simple (no repeated edges like \((B,C)\) then \((C,B)\) in sequence), but not elementary (vertex \(B\) is repeated). However, based on the lecture context, the focus is more on elementary vs non-elementary in the context of cycles.

• Non-Simple Path (and not elementary): \(1 \rightarrow 3 \rightarrow 5 \rightarrow 4 \rightarrow 3 \rightarrow 5 \rightarrow 7 \rightarrow 8\). Edges \((3,5)\) is repeated. Vertices \(\{1, 3, 5, 4, 3, 5, 7, 8\}\), vertices \(3, 5\) are repeated. Cost calculation was shown in the transcription.

Focusing on Elementary Paths

Existence of Optimal Elementary Paths (When an Optimal Path Exists)

When seeking shortest paths, we can often focus on elementary paths. If a shortest path exists, there will always be a shortest path that is also elementary.

Circuits (Cycles) and Negative Costs (Negative Cycles)

The presence of negative cost cycles in a graph complicates the Shortest Path Problem. A negative cycle is a cycle in the graph where the sum of the edge costs is negative. If a path can reach a negative cycle, it can traverse the cycle repeatedly to reduce the total path cost indefinitely, implying no shortest path exists in the traditional sense.

Removing Circuits from Optimal Paths (If They Don’t Improve the Cost)

If an optimal path is not elementary (i.e., it contains a cycle), and if no negative cycles are reachable, we can remove cycles from the path without increasing its cost. If the cycle has a positive cost, removing it will decrease the path cost, contradicting optimality. If it has zero cost, removing it keeps the cost the same but makes the path simpler. If a negative cycle is present and reachable from the source, then the concept of a shortest path needs careful consideration, often implying no lower bound on path cost. However, when we restrict ourselves to elementary paths, even in the presence of negative cycles, a shortest elementary path might still exist because elementary paths, by definition, cannot contain cycles.

Formal Definition of the Shortest Path Problem (SPP)

Input: Directed Graph, Edge Costs, Source Node (s), and Destination Node (t)

Formally, the Shortest Path Problem (SPP) is defined as follows:

Input:

• A directed graph \(G = (V, A)\), where \(V\) is the set of vertices and \(A\) is the set of arcs.

• Edge costs \(C_{ij} \in \mathbb{R}\) for each arc \((i, j) \in A\).

• A source node \(s \in V\) and a destination node \(t \in V\).

Objective: Find a Minimum Cost Elementary Path from s to t

Objective: Find an elementary path \(P\) from \(s\) to \(t\) such that the total cost of the path, \(\sum_{(i,j) \in P} C_{ij}\), is minimized.

Computational Complexity

Impact of Negative Cycles on Problem Difficulty

The presence of negative cycles significantly impacts the computational complexity of the Shortest Path Problem.

NP-Hardness of the General SPP (with Negative Cycles)

In general, finding the shortest path in a graph that may contain negative cycles is an NP-hard problem. This means that there is no known polynomial-time algorithm to solve it for all instances, unless P=NP.

Polynomial Solvability in Specific Cases (Without Negative Cycles)

However, in specific cases, such as when the graph has no negative cycles, or when all edge costs are non-negative, the Shortest Path Problem can be solved in polynomial time. Algorithms like Dijkstra’s algorithm (for non-negative costs) and Bellman-Ford algorithm (for no negative cycles) provide efficient solutions in these cases.

NP-Hardness of the Shortest Path Problem

Reduction from the Hamiltonian Path Problem

The Hamiltonian Path Problem (NP-Complete Problem)

The Hamiltonian Path Problem (HP) is a classic NP-complete problem. It asks whether there exists a Hamiltonian path in a given graph, i.e., a path that visits every vertex exactly once.

Transformation to a Shortest Path Problem Instance

We can demonstrate the NP-hardness of the Shortest Path Problem by reducing the Hamiltonian Path Problem to it. This means we will show how to transform an instance of the Hamiltonian Path Problem into an instance of the Shortest Path Problem such that solving the Shortest Path Problem will also solve the Hamiltonian Path Problem.

Construction of the Transformed Graph

Adding Dummy Source and Destination Nodes (s’ and t’)

Given an instance of the Hamiltonian Path Problem on a graph \(G'=(V', E')\), we construct a directed graph \(G=(V, A)\) for the Shortest Path Problem as follows:

• Vertices \(V = V' \cup \{s', t'\}\), where \(s'\) is a new source node and \(t'\) is a new destination node, and \(V' = \{1, 2, \ldots, N\}\).

Duplicating Edges (Creating Anti-Parallel Arcs with Cost -1)

For each undirected edge \(\{i, j\} \in E'\) in the Hamiltonian Path Problem graph, we create two directed arcs in \(G\): \((i, j)\) and \((j, i)\). We set the cost to \(C_{ij} = C_{ji} = -1\).

Assigning Edge Costs (0 for Added Edges)

• Add arcs from the new source \(s'\) to every node in \(V'\) with cost 0, i.e., \((s', i)\) for all \(i \in V'\) with \(C_{s'i} = 0\).

• Add arcs from every node in \(V'\) to the new destination \(t'\) with cost 0, i.e., \((i, t')\) for all \(i \in V'\) with \(C_{it'} = 0\).

Relationship between Hamiltonian Paths and Shortest Paths

Correspondence between Paths in the Original and Transformed Graphs

A Hamiltonian path of length \(K\) in \(G'\) (if we consider length in terms of edges) corresponds to an elementary path from \(s'\) to \(t'\) in \(G\). If a Hamiltonian path exists in \(G'\), it visits all \(N\) vertices of \(V'\). In the transformed graph \(G\), a path from \(s'\) to \(t'\) that uses \(N-1\) edges from the original graph \(G'\) (each with cost -1) and two edges from the added source/destination connections (each with cost 0) will have a total cost of \(0 + (N-1) \times (-1) + 0 = -(N-1)\).

Implications for Computational Complexity (NP-Hardness)

If we could solve the Shortest Path Problem in polynomial time, we could determine if there is a path from \(s'\) to \(t'\) in \(G\) with cost \(\leq -(N-1)\). If such a path exists, it implies the existence of a Hamiltonian path in \(G'\). Since the Hamiltonian Path Problem is NP-complete, this reduction shows that the Shortest Path Problem in graphs with negative cycles is NP-hard.

Example of the Transformation

Original Graph (Example for Hamiltonian Path)

Consider a graph \(G'\) with vertices \(\{1, 2, 3, 4\}\) and edges \(\{\{1, 2\}, \{2, 3\}, \{2, 4\}, \{3, 4\}, \{1, 3\}\}\) (as depicted in the lecture notes).

Transformed Graph (Corresponding Shortest Path Instance)

We construct a directed graph \(G\) with vertices \(\{1, 2, 3, 4, s', t'\}\). For each edge in \(G'\), we create antiparallel arcs with cost -1. We add arcs from \(s'\) to \(\{1, 2, 3, 4\}\) and from \(\{1, 2, 3, 4\}\) to \(t'\) with cost 0.

Path Lengths and Hamiltonian Path Existence (Relationship)

If a Hamiltonian path exists in \(G'\), say \(1 \rightarrow 2 \rightarrow 4 \rightarrow 3\), then in \(G\), the path \(s' \rightarrow 1 \rightarrow 2 \rightarrow 4 \rightarrow 3 \rightarrow t'\) will have cost \(0 + (-1) + (-1) + (-1) + 0 = -3 = -(4-1)\). If the shortest path from \(s'\) to \(t'\) has cost \(-(N-1)\), where \(N=4\), then a Hamiltonian path exists in \(G'\).

General NP-Hardness

Implications of Negative Cycles (Making the Problem Difficult)

The NP-hardness arises from the combination of seeking elementary paths and the potential presence of negative cycles. Negative cycles introduce complexity because paths can become arbitrarily short by traversing these cycles repeatedly, unless we restrict ourselves to elementary paths.

Maximum Path Problem (Also NP-Hard in General)

Relatedly, the Maximum Path Problem (finding the longest path) is also NP-hard in general graphs. By negating all edge costs, a maximum path problem can be transformed into a minimum path problem, and vice versa.

Polynomial Solvability

Conditions for Polynomial Time Solutions

Non-Negative Edge Costs (Dijkstra’s Algorithm is Applicable)

If all edge costs are non-negative (\(C_{ij} \geq 0\) for all arcs), Dijkstra’s algorithm can efficiently find the shortest paths from a single source in polynomial time.

Acyclic Graphs (Topological Sort and Dynamic Programming)

In directed acyclic graphs (DAGs), shortest paths can be found in polynomial time using topological sorting and dynamic programming, even with negative edge costs (as long as there are no negative cycles, which is guaranteed in a DAG).

Graphs without Negative Cycles (Bellman-Ford Algorithm)

For graphs that may have negative edge costs but no negative cycles, the Bellman-Ford algorithm can find shortest paths from a single source in polynomial time.

Focus on Polynomial Algorithms

Dijkstra’s Algorithm (Efficient for Non-Negative Edge Costs)

Dijkstra’s algorithm is a highly efficient algorithm for finding single-source shortest paths in graphs with non-negative edge costs.

Other Polynomial Algorithms (For Specific Graph Structures)

For specific graph structures like DAGs or graphs without negative cycles, polynomial-time algorithms exist.

Preprocessing and Simplifications

Removing Incoming Edges to the Source Node (s)

For finding paths starting from a source node \(s\), incoming edges to \(s\) are irrelevant and can be removed without affecting the shortest paths from \(s\).

Removing Outgoing Edges from the Destination Node (t)

Similarly, for paths ending at a destination node \(t\), outgoing edges from \(t\) are irrelevant and can be removed.

Path Representation

Sequence of Vertices (Nodes) in a Path

A path can be represented as a sequence of vertices visited in order.

Relationship between Vertices and Edges (for Elementary Paths)

For elementary paths, the sequence of vertices uniquely determines the sequence of edges in the path.

Integer Linear Programming (ILP) Formulation

Binary Variables for Edges (\(x_{ij}\) = 1 if edge (i,j) is in the path, 0 otherwise)

We can formulate the Shortest Path Problem as an Integer Linear Program (ILP). We introduce binary variables \(x_{ij}\) for each arc \((i, j) \in A\), where \(x_{ij} = 1\) if arc \((i, j)\) is part of the shortest path, and \(x_{ij} = 0\) otherwise.

Constraints for a Valid Path (Flow Conservation, Source/Destination)

We need to define constraints to ensure that the selected arcs form a valid path from source \(s\) to destination \(t\). These constraints include flow conservation and source/destination conditions.

Objective Function (Minimize Total Path Cost)

The objective is to minimize the total cost of the path, which can be expressed as: \[\text{Minimize } \sum_{(i,j) \in A} C_{ij} x_{ij}\]

Constraints for a Valid Path

One Outgoing Edge from the Source Node (s)

Constraint for the source node \(s\): \[\sum_{j:(s,j) \in A} x_{sj} = 1 \label{eq:source_constraint}\] This ensures that exactly one edge leaves the source node.

One Incoming Edge to the Destination Node (t)

Constraint for the destination node \(t\): \[\sum_{i:(i,t) \in A} x_{it} = 1 \label{eq:destination_constraint}\] This ensures that exactly one edge enters the destination node.

Flow Conservation (In-Degree = Out-Degree for Intermediate Nodes)

For every node \(v \in V \setminus \{s, t\}\), the flow conservation constraint is: \[\sum_{j:(v,j) \in A} x_{vj} - \sum_{i:(i,v) \in A} x_{iv} = 0 \label{eq:flow_conservation}\] This ensures that for any intermediate node, the number of incoming edges in the path equals the number of outgoing edges in the path.

Subtour Elimination Constraints (Preventing Cycles in the Solution)

To ensure that the solution is an elementary path (and not a collection of disjoint cycles and paths), we need subtour elimination constraints. For every subset of vertices \(S \subseteq V \setminus \{s, t\}\), \(S \neq \emptyset\), we must have: \[\sum_{(i,j) \in A: i \in S, j \in S} x_{ij} \leq |S| - 1 \label{eq:subtour_elimination}\] These constraints prevent cycles within any subset of nodes that does not include the source or destination.

Lemma on Graphs with Equal In-Degree and Out-Degree

Statement of the Lemma (Decomposition into Elementary Circuits)

Let \(G' = (V', A')\) be a directed graph such that for every vertex \(v \in V'\), the in-degree of \(v\) is equal to the out-degree of \(v\). Then, the set of arcs \(A'\) can be partitioned into a set of arc-disjoint elementary circuits.

Proof by Induction on the Number of Edges (Arcs)

The proof is by induction on the number of arcs in \(A'\).

• Base Case: If \(|A'| = 0\), the set of arcs is empty, and it is trivially partitioned into zero elementary circuits.

• Inductive Step: Assume the lemma holds for all graphs with fewer than \(M\) arcs that satisfy the degree condition. Consider a graph \(G'\) with \(|A'| = M\) arcs. Choose a vertex \(v_0\) with a positive degree (if any arcs exist, such a vertex must exist). Starting from \(v_0\), traverse an outgoing arc to \(v_1\), then an outgoing arc from \(v_1\) to \(v_2\), and so on. Since the out-degree is always positive when the in-degree is positive, we can continue this process. Because the number of vertices is finite, we must eventually revisit a vertex, forming a cycle. Let \(C\) be the first elementary cycle formed. Remove the arcs of \(C\) from \(G'\). The resulting graph \(G''\) still satisfies the condition that in-degree equals out-degree for every vertex (because removing a cycle reduces both in-degree and out-degree by 1 for each vertex in the cycle). Since \(G''\) has fewer arcs than \(G'\), by the induction hypothesis, the arcs of \(G''\) can be partitioned into elementary circuits. Adding \(C\) to this partition gives a partition of the arcs of \(G'\) into elementary circuits.

Proof of Correctness of the ILP Formulation

Adding an Edge from Destination to Source (Creating a Cycle)

Consider a set of arcs \(X\) that satisfies constraints [eq:source_constraint], [eq:destination_constraint], and [eq:flow_conservation]. Add a dummy arc from \(t\) to \(s\), say \((t, s)\), to the graph formed by arcs in \(X\).

Decomposition into Elementary Circuits (Using the Lemma)

In the graph formed by \(X \cup \{(t, s)\}\), every vertex has equal in-degree and out-degree (specifically, for \(s\) and \(t\), due to constraints [eq:source_constraint] and [eq:destination_constraint], and for intermediate nodes due to [eq:flow_conservation]). By Lemma [lemma:cycle_decomposition], the arcs in \(X \cup \{(t, s)\}\) can be decomposed into elementary circuits.

Elimination of Subtours (Ensuring a Single Path from s to t)

The subtour elimination constraints [eq:subtour_elimination] ensure that there is only one circuit in this decomposition that contains the arc \((t, s)\). If there were another circuit, it would be entirely within a subset of vertices \(S \subseteq V \setminus \{s, t\}\), violating constraint [eq:subtour_elimination]. Therefore, after removing the arc \((t, s)\), what remains from the circuit containing \((t, s)\) is a single elementary path from \(s\) to \(t\).

Complete ILP Formulation

Objective Function (Minimize Sum of Edge Costs * \(x_{ij}\))

\[\text{Minimize } \sum_{(i,j) \in A} C_{ij} x_{ij}\]

Constraints (Flow Conservation, Source/Destination, Subtour Elimination)

Subject to: \[\begin{aligned} \sum_{j:(s,j) \in A} x_{sj} &= 1 \\ \sum_{i:(i,t) \in A} x_{it} &= 1 \\ \sum_{j:(v,j) \in A} x_{vj} - \sum_{i:(i,v) \in A} x_{iv} &= 0, \quad \forall v \in V \setminus \{s, t\} \\ \sum_{(i,j) \in A: i \in S, j \in S} x_{ij} &\leq |S| - 1, \quad \forall S \subseteq V \setminus \{s, t\}, S \neq \emptyset \\ x_{ij} &\in \{0, 1\}, \quad \forall (i, j) \in A \end{aligned}\]

Exponential Number of Subtour Elimination Constraints (Requires Separation)

The number of subtour elimination constraints is exponential in the number of vertices, making it impractical to list them all explicitly for large graphs. In practice, these constraints are handled using separation algorithms within a branch-and-cut framework.

Necessity of Subtour Elimination Constraints

Example of a Graph with a Negative Cycle (Illustrating the Problem)

Consider the example graph where without subtour elimination, a solution might include a negative cycle and a disconnected path, leading to a suboptimal result. (Refer to the example discussed in the lecture notes, Figure B vs Figure A).

Solution without Subtour Elimination (Incorrect Result with a Cycle)

Without subtour elimination constraints, the ILP might find a solution that is not a single path from \(s\) to \(t\),Without subtour elimination constraints, the ILP might find a solution that is not a single path from \(s\) to \(t\), but rather a combination of a path and one or more cycles, especially negative cycles, if present. In the example, the solution might pick edges (1,4), (4,6) and the cycle (2,3), (3,5), (5,2), resulting in a total cost of 1, which is incorrect.

Solution with Subtour Elimination (Correct Result - Elementary Path)

With subtour elimination constraints, the ILP is forced to find a solution that is a single elementary path from \(s\) to \(t\), ensuring the correctness of the shortest path solution. In the example, adding the constraint \(x_{23} + x_{35} + x_{52} \leq 2\) would prevent the incorrect solution.

Total Unimodularity

Node-Arc Incidence Matrix (Representing Graph Connectivity)

The constraints [eq:source_constraint], [eq:destination_constraint], and [eq:flow_conservation] can be represented using the node-arc incidence matrix of the graph.

Properties of the Incidence Matrix (Entries -1, 0, +1)

The node-arc incidence matrix \(M\) has entries from \(\{-1, 0, +1\}\). For each arc \((i, j)\), the column in \(M\) has a \(+1\) in row \(i\), a \(-1\) in row \(j\), and 0 elsewhere.

Relationship to the ILP Formulation (Flow Conservation Constraints)

The flow conservation constraints are directly derived from the properties of the node-arc incidence matrix. The system \(Mx = b\) (where \(b\) is appropriately defined) represents the flow conservation and source/destination constraints.

Example of the Incidence Matrix

Graph Example (with Source and Destination Nodes)

Consider a graph with nodes \(V = \{s, 1, 2, 3, 4, t\}\) and arcs \(A = \{(s,1), (s,2), (1,t), (2,3), (3,4), (3,t), (4,2)\}\).

Incidence Matrix Construction (Rows for Nodes, Columns for Edges)

The incidence matrix \(M\) is constructed as follows:

	(s,1)	(s,2)	(1,t)	(2,3)	(3,4)	(3,t)	(4,2)
s	+1	+1	0	0	0	0	0
1	-1	0	+1	0	0	0	0
2	0	-1	0	+1	0	0	-1
3	0	0	0	-1	+1	+1	0
4	0	0	0	0	-1	0	+1
t	0	0	-1	0	0	-1	0

Relationship to the Flow Conservation Constraints (Matrix-Vector Product)

Let \(x\) be the vector of binary variables corresponding to the arcs. The matrix-vector product \(Mx\) represents the flow conservation constraints. For example, for node 3, the corresponding row in \(M\) yields the equation \(-x_{23} + x_{34} + x_{3t} = 0\), which is the flow conservation constraint for node 3.

Conclusion on Polynomial Solvability

Implications of Total Unimodularity (Integer Solutions from LP Relaxation)

The node-arc incidence matrix is totally unimodular. This property implies that if we relax the integrality constraints and solve the Linear Programming (LP) relaxation of the ILP (i.e., replace \(x_{ij} \in \{0, 1\}\) with \(0 \leq x_{ij} \leq 1\)), and if the right-hand side vector \(b\) is integer, then the optimal solution to the LP relaxation will also be integer, and thus, it will be an optimal solution to the original ILP (without subtour elimination constraints).

Polynomial Solvability without Negative Cycles (Using Linear Programming)

For graphs without negative cycles, if we ignore the subtour elimination constraints, the remaining ILP formulation, when relaxed to an LP, can be solved in polynomial time using linear programming algorithms. Due to total unimodularity, this LP solution will be integer and thus provide the shortest path. However, with negative cycles, subtour elimination constraints become necessary, and the problem becomes NP-hard in general, requiring more complex solution methods than simple LP.

Conclusion

In this lecture, we have introduced the Shortest Path Problem, a critical problem in combinatorial optimization with wide-ranging applications. We explored its definition, variations, and the concept of optimality. We discussed graph representations and the crucial role of edge costs, including the complexities introduced by negative costs and cycles. We highlighted the distinction between simple and elementary paths and justified our focus on elementary paths for finding optimal solutions.

We examined the computational complexity of the SPP, demonstrating its NP-hardness in the general case, particularly when negative cycles are present. This NP-hardness was shown through a reduction from the Hamiltonian Path Problem. Conversely, we noted that under specific conditions, such as non-negative edge costs or the absence of negative cycles, the SPP becomes polynomially solvable.

Finally, we formulated the Shortest Path Problem as an Integer Linear Program, detailing the necessary constraints for flow conservation, source and destination conditions, and the essential subtour elimination constraints to ensure elementary paths. We discussed the total unimodularity of the node-arc incidence matrix and its implications for polynomial solvability in cases without negative cycles using linear programming.

• The Shortest Path Problem is fundamental in network optimization and has numerous real-world applications.

• The presence of negative cycles dramatically increases the problem’s complexity, making it NP-hard in general.

• For graphs without negative cycles, polynomial-time algorithms and linear programming approaches can efficiently find shortest paths.

• Subtour elimination constraints are crucial for ensuring elementary path solutions in ILP formulations, especially in the presence of negative cycles, but they also lead to exponential complexity.

• Total unimodularity of the node-arc incidence matrix is a key property that enables polynomial-time solutions for certain cases of the Shortest Path Problem using linear programming.

• How do Dijkstra’s algorithm and Bellman-Ford algorithm solve the Shortest Path Problem in polynomial time under specific conditions?

• What are efficient algorithms for solving the Shortest Path Problem in graphs without negative cycles, beyond linear programming?

• How are subtour elimination constraints handled in practice for solving the NP-hard Shortest Path Problem?

• What are other formulations and approaches for solving the Shortest Path Problem, especially in complex scenarios?