PAMANTASAN NG LUNGSOD NG MUNTINLUPA

LEARNING COLLEGE OF INFORMATION TECHNOLOGY AND

MODULE COMPUTER STUDIES
University Road, Poblacion, Muntinlupa City

QD/CITCS/0 Course Title: ALGORITHMS AND COMPLEXITY

Issue No. 0 Revision No. 0 Effectivity Date 07 September 2020 Page No. 1 of 14

FACILITATING LEARNER-CENTERED LEARNING

(Self-Learning Module)

ALGCPLX-
ALGORITHMS AND
COMPLEXITY

Asst. Prof. FE L. HABLANIDA, MSCS

Course Instructor
 PAMANTASAN NG LUNGSOD NG MUNTINLUPA
LEARNING COLLEGE OF INFORMATION TECHNOLOGY AND
MODULE COMPUTER STUDIES
University Road, Poblacion, Muntinlupa City

QD/CITCS/0 Course Title: ALGORITHMS AND COMPLEXITY

Issue No. 0 Revision No. 0 Effectivity Date 07 September 2020 Page No. 2 of 14

GRAPH ALGORITHMS
(SHORTEST PATH ALGORITHMS)

LEARNING OUTCOMES:

At the end of the lesson, the learner will be able to:

• Implement algorithms to find shortest paths in graphs
• Analyze the time and space complexity of these shortest path algorithms.
• Construct and interpret shortest path trees generated by algorithms.

LESSON ROADMAP:

1. Shortest Path Algorithms

• Dijkstra's Algorithm
• Bellman-Ford Algorithm
• Floyd-Warshall Algorithm
• A* (A-Star) Algorithm
• Johnson’s Algorithm
 PAMANTASAN NG LUNGSOD NG MUNTINLUPA
LEARNING COLLEGE OF INFORMATION TECHNOLOGY AND
MODULE COMPUTER STUDIES
University Road, Poblacion, Muntinlupa City

QD/CITCS/0 Course Title: ALGORITHMS AND COMPLEXITY

Issue No. 0 Revision No. 0 Effectivity Date 07 September 2020 Page No. 3 of 14

DISCUSSION:

SHORTEST PATH ALGORITHMS

Shortest Path Algorithms are used to find the minimum-cost path between nodes in a
weighted graph. They are essential in fields like navigation, route planning, networking,
operations research, and AI.

 Dijkstra’s Algorithm
Dijkstra’s Algorithm is used to find the shortest path from a single source to all other
vertices in a weighted graph with non-negative edge weights.
• It produces a shortest-path tree showing the minimum cost to reach each node.
• Use this algorithm when:
o The graph is weighted

o All weights are non-negative

o You need the shortest paths from one source to all vertices

➢ Concept
a. Maintain a distance array to record the shortest known distance to each vertex.
b. Always choose the unvisited vertex with the smallest distance (greedy choice).
c. Update (relax) the distances of its neighbors.
d. Repeat until all vertices are processed.
➢ Steps of Dijkstra’s Algorithm
1. Initialize
o Set distance of source = 0

o Set the distance of all other vertices = ∞

o Mark all vertices as unvisited

2. Select the unvisited vertex with the smallest distance value.

3. Relax Edges:
o For each neighbor of the selected vertex, check if going through this vertex gives a

shorter path.
 PAMANTASAN NG LUNGSOD NG MUNTINLUPA
LEARNING COLLEGE OF INFORMATION TECHNOLOGY AND
MODULE COMPUTER STUDIES
University Road, Poblacion, Muntinlupa City

QD/CITCS/0 Course Title: ALGORITHMS AND COMPLEXITY

Issue No. 0 Revision No. 0 Effectivity Date 07 September 2020 Page No. 4 of 14

4. Mark the current vertex as visited.

5. Repeat Steps 2–4 until all vertices are visited.
➢ Advantages
1. Fast and efficient for large graphs with non-negative weights

2. Guarantees shortest paths

➢ Limitations
1. Cannot handle negative weight edges

2. Use Bellman–Ford if negative weights exist

➢ Time Complexity:
• With min-heap: O((V + E) log V).

 Bellman–Ford Algorithm
The Bellman–Ford Algorithm is a shortest-path algorithm used to compute the
minimum distance from a single source to all other vertices in a weighted graph.
• Unlike Dijkstra’s algorithm, it can handle:

o Negative edge weights

o Detection of negative-weight cycles

• Finds the shortest path from a single source to all other vertices in graphs with negative

edge weights.
• A negative edge weight means an edge whose cost is less than zero.

➢ Use When:
1. Graph may contain negative edge weights.

2. You need to detect negative cycles.

3. Needed when negative edges are present or when cycle detection is required.

➢ Key Ideas:
1. Dynamic programming approach.

2. Relaxes all edges repeatedly.

3. A final pass checks for negative weight cycles (cycles whose total weight is negative).
 PAMANTASAN NG LUNGSOD NG MUNTINLUPA
LEARNING COLLEGE OF INFORMATION TECHNOLOGY AND
MODULE COMPUTER STUDIES
University Road, Poblacion, Muntinlupa City

QD/CITCS/0 Course Title: ALGORITHMS AND COMPLEXITY

Issue No. 0 Revision No. 0 Effectivity Date 07 September 2020 Page No. 5 of 14

➢ Algorithm Steps
Given a graph with:
• V = number of vertices
• E = number of edges
• Source vertex = S
1. Initialize distances

2. Relax all edges V−1 times

• For i = 1 to V–1:
o For each edge (u, v) with weight w:

If distance[u] + w < distance[v], update:

3. Check for negative cycles

• Go through all edges one more time:
o If a relaxation is still possible, the graph has a negative cycle.

➢ Time Complexity
Operation Complexity
Relax edges V–1 times O(V × E)
Check for negative cycles O(E)
Total O(V × E)

➢ Examples of where they appear:

• Financial gain/loss graphs

• Energy-saving or cost-reduction networks

• Some dynamic programming graph models

➢ Advantages
1. Works with negative weights.
 PAMANTASAN NG LUNGSOD NG MUNTINLUPA
LEARNING COLLEGE OF INFORMATION TECHNOLOGY AND
MODULE COMPUTER STUDIES
University Road, Poblacion, Muntinlupa City

QD/CITCS/0 Course Title: ALGORITHMS AND COMPLEXITY

Issue No. 0 Revision No. 0 Effectivity Date 07 September 2020 Page No. 6 of 14

2. Can detect negative weight cycles—Dijkstra cannot.

➢ Disadvantages:
1. Slower than Dijkstra’s Algorithm.

 Floyd–Warshall Algorithm
The Floyd–Warshall Algorithm is a dynamic programming algorithm used to compute
the shortest paths between all pairs of vertices in a weighted graph.
• It works for:

o Directed or undirected graphs

o Graphs with negative edge weights

o Detecting negative cycles

➢ Characteristics
1. Computes all-pairs shortest paths (APSP)
2. Works with negative weights
3. Does not work properly if a negative cycle exists (but it can detect them)
➢ Use When
1. You need the shortest paths between all pairs of vertices.
2. Graph may have negative weights but no negative cycles.
➢ Key Ideas
1. Dynamic programming using a matrix.
2. Tries all possible intermediate vertices.
3. The algorithm incrementally improves an N × N distance matrix by checking whether
the path from i → k → j is shorter than the current i → j path.
4. For each intermediate vertex k, update:

➢ Algorithm Steps
Given:
• A graph with V vertices
 PAMANTASAN NG LUNGSOD NG MUNTINLUPA
LEARNING COLLEGE OF INFORMATION TECHNOLOGY AND
MODULE COMPUTER STUDIES
University Road, Poblacion, Muntinlupa City

QD/CITCS/0 Course Title: ALGORITHMS AND COMPLEXITY

Issue No. 0 Revision No. 0 Effectivity Date 07 September 2020 Page No. 7 of 14

• A distance matrix where:

o dist[i][i] = 0

o dist[i][j] = weight(i→j) if an edge exists

o dist[i][j] = ∞ if no edge exists

1. Initialization
• Start with the adjacency matrix.

2. Choose each vertex k as intermediate

For k = 1 to V:
For i = 1 to V:
For j = 1 to V:
Update shortest path:

3. Negative cycle check

If dist[i][i] < 0 for any vertex i, then a negative cycle is detected.
➢ Time Complexity
• O(V³).

➢ Advantages
1. Simple and elegant dynamic programming solution
2. Finds shortest paths for ALL vertex pairs
3. Handles negative edges
4. Detects negative cycles
➢ Disadvantages
1. Slow for large graphs: O(V³)
2. Not suitable for sparse, huge networks
 PAMANTASAN NG LUNGSOD NG MUNTINLUPA
LEARNING COLLEGE OF INFORMATION TECHNOLOGY AND
MODULE COMPUTER STUDIES
University Road, Poblacion, Muntinlupa City

QD/CITCS/0 Course Title: ALGORITHMS AND COMPLEXITY

Issue No. 0 Revision No. 0 Effectivity Date 07 September 2020 Page No. 8 of 14

➢ Floyd–Warshall vs Dijkstra vs Bellman–Ford

Feature Floyd–Warshall Dijkstra Bellman–Ford
Computes All-pairs Single-source Single-source
Negative weights ✔ ✘ ✔
Negative cycles ✔ detects ✘ ✔ detects
Complexity O(V³) O(E log V) O(VE)

 A* (A-Star) Algorithm
The A* Algorithm is a best-first search algorithm used to find the shortest path
between two nodes in a graph.
• It is widely used in:

o Artificial Intelligence

o Robotics

o Pathfinding in games

o Navigation systems (GPS)

• A* combines:

o The actual cost to reach a node, g(n)

o A heuristic estimate of the cost from that node to the goal, h(n)

o These form the evaluation function:

➢ Key Idea
1. A* chooses the next node with the lowest f(n) value.
2. It balances:
• g(n): cost from start

• h(n): how close the node appears to the goal

3. Uses a heuristic (e.g., Euclidean distance) to guide the search.

4. Faster than Dijkstra when the heuristic is strong.
 PAMANTASAN NG LUNGSOD NG MUNTINLUPA
LEARNING COLLEGE OF INFORMATION TECHNOLOGY AND
MODULE COMPUTER STUDIES
University Road, Poblacion, Muntinlupa City

QD/CITCS/0 Course Title: ALGORITHMS AND COMPLEXITY

Issue No. 0 Revision No. 0 Effectivity Date 07 September 2020 Page No. 9 of 14
➢ Use When
1. You need a fast shortest path search with a heuristic (e.g., maps).
2. Used in navigation systems and games.
➢ Algorithm Steps
1. Initialize:
• Add the start node to the open list.
• Closed list is empty.
2. Loop until the open list is empty:
• Pick the node with the smallest f(n) from the open list → call it current.
• If current is the goal, stop (path found).
• Move current to the closed list.
• For each neighbor of the current:
• Compute g, h, and f values.
• If neighbor is in the closed list → skip.
• If neighbor is not in open list → add it.
• If neighbor is in open list but new g is cheaper → update it.
3. Reconstruct the path from the goal to start using parent pointers.
➢ Admissible Heuristic
1. A heuristic is admissible if:

Examples:
▪ Manhattan distance (grid movement: up, down, left, right)
▪ Euclidean distance (straight-line distance)
▪ Using an admissible heuristic ensures optimality.
▪ Grid Pathfinding
 PAMANTASAN NG LUNGSOD NG MUNTINLUPA
LEARNING COLLEGE OF INFORMATION TECHNOLOGY AND
MODULE COMPUTER STUDIES
University Road, Poblacion, Muntinlupa City

QD/CITCS/0 Course Title: ALGORITHMS AND COMPLEXITY

Issue No. 0 Revision No. 0 Effectivity Date 07 September 2020 Page No. 10 of 14

Grid:

▪ Heuristic: Manhattan Distance

o Step 1: Start at S
Compute f = g + h.
At S:

Neighbors are evaluated similarly.

o Step 2: Choose the lowest f(n)
Expand nodes by increasing f.
o Step 3: Continue search
A* expands nodes closer to the goal (guided by the heuristic) and avoids unnecessary
paths.
o Step 4: Reconstruct path
A* efficiently finds the shortest path.
➢ Advantages
1. Faster than Dijkstra (due to heuristic guiding the search)
2. Guarantees an optimal solution if the heuristic is admissible
3. Works well in real-time applications
4. Good for large graphs (e.g., gaming maps)
➢ Disadvantages
1. Performance depends heavily on heuristic quality
2. Can still be expensive in the worst case
3. Requires good memory for open/closed lists
 PAMANTASAN NG LUNGSOD NG MUNTINLUPA
LEARNING COLLEGE OF INFORMATION TECHNOLOGY AND
MODULE COMPUTER STUDIES
University Road, Poblacion, Muntinlupa City

QD/CITCS/0 Course Title: ALGORITHMS AND COMPLEXITY

Issue No. 0 Revision No. 0 Effectivity Date 07 September 2020 Page No. 11 of 14

➢ A* Pseudocode
 PAMANTASAN NG LUNGSOD NG MUNTINLUPA
LEARNING COLLEGE OF INFORMATION TECHNOLOGY AND
MODULE COMPUTER STUDIES
University Road, Poblacion, Muntinlupa City

QD/CITCS/0 Course Title: ALGORITHMS AND COMPLEXITY

Issue No. 0 Revision No. 0 Effectivity Date 07 September 2020 Page No. 12 of 14

➢ A* vs Dijkstra vs Greedy Best-First Search

Feature A* Dijkstra Greedy Best-First
Uses g(n) ✔ Yes ✔ Yes ✘ No
Uses h(n) ✔ Yes ✘ No ✔ Yes
Optimal ✔ Yes (if admissible) ✔ Yes ✘ No
Speed Faster than Dijkstra Slower Fastest but not optimal

➢ Time complexity:
• Depends on heuristic, worst case similar to Dijkstra.

 Johnson’s Algorithm
Johnson’s Algorithm is an efficient algorithm used to compute the shortest paths
between all pairs of vertices in a sparse graph (a graph with relatively few edges).
• It combines:

• Bellman–Ford Algorithm
• Dijkstra’s Algorithm
• Reweighting using a potential function
• This allows it to work even with negative edge weights, as long as there are no negative

cycles.
➢ When to Use Johnson’s Algorithm
Use Johnson’s Algorithm when:
1. The graph is sparse (E ≈ V or moderately larger)
2. The graph has negative edge weights
3. You need all-pairs shortest paths (APSP)
4. You want better performance than the O(V³) Floyd–Warshall algorithm
5. You need all-pairs shortest paths in a sparse graph with possible negative weights.
6. More efficient than Floyd–Warshall for large, sparse graphs.
➢ Key Ideas:
1. Johnson’s Algorithm uses reweighting so that:
• All edge weights become non-negative
• Shortest paths are preserved
 PAMANTASAN NG LUNGSOD NG MUNTINLUPA
LEARNING COLLEGE OF INFORMATION TECHNOLOGY AND
MODULE COMPUTER STUDIES
University Road, Poblacion, Muntinlupa City

QD/CITCS/0 Course Title: ALGORITHMS AND COMPLEXITY

Issue No. 0 Revision No. 0 Effectivity Date 07 September 2020 Page No. 13 of 14

2. Reweights edges using Bellman–Ford and then runs Dijkstra.

3. After reweighting, Dijkstra’s Algorithm can be used efficiently for each vertex.
➢ Algorithm Steps

1. Add a new vertex s

• Add a new vertex s connected to every other vertex v with edge weight 0.
• This is needed for Bellman–Ford.
2. Run Bellman–Ford from vertex s
• Bellman–Ford computes a potential function (h):

• These values help in reweighting.

• If Bellman–Ford detects a negative cycle, Johnson’s Algorithm stops.
3. Reweight all edges
• For every edge u → v with weight w(u, v):

• After reweighting:
o All new weights w'(u, v) are guaranteed to be non-negative
o Shortest paths remain consistent
4. Run Dijkstra’s Algorithm from each vertex
• Because weights are now non-negative, Dijkstra’s Algorithm works efficiently.
• Do this for each vertex u:

5. Adjust distances back to original weights

• Convert the reweighted results back using:

➢ Time Complexity:
• O(V² log V + V × E).
 PAMANTASAN NG LUNGSOD NG MUNTINLUPA
LEARNING COLLEGE OF INFORMATION TECHNOLOGY AND
MODULE COMPUTER STUDIES
University Road, Poblacion, Muntinlupa City

QD/CITCS/0 Course Title: ALGORITHMS AND COMPLEXITY

Issue No. 0 Revision No. 0 Effectivity Date 07 September 2020 Page No. 14 of 14

➢ Advantages
1. Handles negative weights
2. Much faster than Floyd–Warshall for sparse graphs
3. Uses efficient Dijkstra after reweighting
4. Good for large real-world networks
➢ Disadvantages
1. Cannot handle negative cycles
2. More complex than other APSP algorithms
3. Needs both Bellman–Ford and Dijkstra implementations

REFERENCES:

Introduction to Algorithms, Fourth Edition, Thomas H. Cormen, Charles E. Leiserson, Ronald

L. Rivest, Clifford Stein (2022), The MIT Press

“Design and Analysis of Algorithms”, 3rd Edition, Levitin, Anany (ISBN 10: 013-231681-1,
ISBN 13: 978-0-13231681-1), 283-289

Computational Complexity: A Conceptual Perspective. Oded Goldreich. (2008).

Cambridge University Press.

`12. John Carey, Shreyans Doshi, & Payas Rajan. (2019). C++ Data Structures and
Algorithm Design Principles: Leverage the Power of Modern C++ to Build Robust and
Scalable Applications. Packt Publishing.