We revisit the shortest paths problem, considering the case where the input is a directed minor-free graph with negative arc lengths (but no negative-length cycles).In Lecture 14, we saw almost-linear-time algorithms for the case of planar and bounded-genus graphs. Currently, comparable bounds for minor-free graphs are not known. We shall discuss Goldberg's algorithm, a shortest-path algorithm for general graphs with integer lengths, whose running time depends logarithmically on the magnitude of the largest negative arc length. By exploiting separators (Lecture 6), it runs faster on minor-free graphs than on general graphs, but it still requires superlinear time.

Lectures:- Play ►
### Positive Definite Matrices K = A'CA

00:59:50Gilbert StrangWe revisit the shortest paths problem, considering the case where the input is a directed minor-free graph with negative arc lengths (but no negative-length cycles).In Lecture 14, we saw almost-linear-time algorithms for the case of planar and bounded-genus graphs. Currently, comparable bounds for minor-free graphs are not known. We shall discuss Goldberg's algorithm, a shortest-path algorithm for general graphs with integer lengths, whose running time depends logarithmically on the magnitude of the largest negative arc length. By exploiting separators (Lecture 6), it runs faster on minor-free graphs than on general graphs, but it still requires superlinear time.

- Play ►
### Network Applications: A = Incidence Matrix

00:57:15Gilbert StrangWe revisit the shortest paths problem, considering the case where the input is a directed minor-free graph with negative arc lengths (but no negative-length cycles).In Lecture 14, we saw almost-linear-time algorithms for the case of planar and bounded-genus graphs. Currently, comparable bounds for minor-free graphs are not known. We shall discuss Goldberg's algorithm, a shortest-path algorithm for general graphs with integer lengths, whose running time depends logarithmically on the magnitude of the largest negative arc length. By exploiting separators (Lecture 6), it runs faster on minor-free graphs than on general graphs, but it still requires superlinear time.

- Play ►
### Applications to Linear Estimation: Least Squares

01:07:47Gilbert Strang - Play ►
### Applications to Dynamics: Eigenvalues of K, Solution of MU'' + KU = F(T)

01:07:01Gilbert Strang - Play ►
### Underlying Theory: Applied Linear Algebra

01:05:27Gilbert Strang - Play ►
### Discrete Vs. Continuous: Differences and Derivatives

01:07:35Gilbert Strang - Play ►
### Applications to Boundary Value Problems: Laplace Equation

01:05:56Gilbert Strang - Play ►
### Solutions of Laplace Equation: Complex Variables

01:09:58Gilbert Strang - Play ►
### Delta Function and Green's Function

01:00:55Gilbert Strang - Play ►
### initial Value Problems: Wave Equation and Heat Equation

01:06:08Gilbert Strang - Play ►
### Solutions of initial Value Problems: Eigenfunctions

01:06:13Gilbert Strang - Play ►
### Numerical Linear Algebra: Orthogonalization and A = QR

01:11:02Gilbert Strang - Play ►
### Numerical Linear Algebra: SVD and Applications

01:00:58Gilbert Strang - Play ►
### Numerical Methods in Estimation: Recursive Least Squares and Covariance Matrix

01:06:32Gilbert Strang - Play ►
### Dynamic Estimation: Kalman Filter and Square Root Filter

01:02:22Gilbert Strang - Play ►
### Finite Difference Methods: Equilibrium Problems

01:05:16Gilbert Strang - Play ►
### Finite Difference Methods: Stability and Convergence

01:07:27Gilbert Strang - Play ►
### Optimization and Minimum Principles: Euler Equation

01:08:17Gilbert Strang - Play ►
### Finite Element Method: Equilibrium Equations

01:01:47Gilbert Strang - Play ►
### Spectral Method: Dynamic Equations

01:09:48Gilbert Strang - Play ►
### Fourier Expansions and Convolution

01:02:34Gilbert Strang - Play ►
### Fast Fourier Transform and Circulant Matrices

01:15:39Gilbert Strang - Play ►
### Discrete Filters: Lowpass and Highpass

01:00:24Gilbert Strang - Play ►
### Filters in the Time and Frequency Domain

01:21:59Gilbert Strang - Play ►
### Filter Banks and Perfect Reconstruction

00:55:21Gilbert Strang - Play ►
### Multiresolution, Wavelet Transform and Scaling Function

01:15:49Gilbert Strang - Play ►
### Splines and Orthogonal Wavelets: Daubechies Construction

01:04:34Gilbert Strang - Play ►
### Applications in Signal and Image Processing: Compression

01:14:04Gilbert Strang - Play ►
### Network Flows and Combinatorics: Max Flow = Min Cut

01:16:30Gilbert Strang - Play ►
### Simplex Method in Linear Programming

01:05:08Gilbert Strang - Play ►
### Nonlinear Optimization: Algorithms and Theory

00:50:14Gilbert Strang