Scribd
Upload
2 views3 pages

Algorithm Assignment1

The document outlines three algorithms for finding shortest paths in graphs: Dijkstra's Algorithm for non-negative weights, Bellman-Ford Algorithm for graphs with negative weights, and Floyd-Warshall Algorithm for all pairs of vertices. Each algorithm includes its purpose, steps, and time complexity. Dijkstra's has a time complexity of O(V²) or O((V+E) log V), Bellman-Ford is O(V·E), and Floyd-Warshall is O(V³).

Uploaded by

hussein adebayo
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
2 views3 pages

Algorithm Assignment1

The document outlines three algorithms for finding shortest paths in graphs: Dijkstra's Algorithm for non-negative weights, Bellman-Ford Algorithm for graphs with negative weights, and Floyd-Warshall Algorithm for all pairs of vertices. Each algorithm includes its purpose, steps, and time complexity. Dijkstra's has a time complexity of O(V²) or O((V+E) log V), Bellman-Ford is O(V·E), and Floyd-Warshall is O(V³).

Uploaded by

hussein adebayo
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

1.

DIJKSTRA'S ALGORITHM
Purpose: Finds shortest paths from a source vertex to all other vertices in a graph
with non-negative edge weights.
Steps:
1. Initialize distances: set source distance = 0, others = ∞.
2. Use a priority queue (min-heap) to pick the unvisited vertex with smallest
distance.
3. For each neighbor of this vertex, if dist[u] + weight(u, v) < dist[v], update dist[v].
4. Mark vertex as visited, repeat until all vertices are processed.
Time Complexity: O(V²) for simple array, O((V+E) log V) with min-heap.

Dijkstra C Programming Implementation


2. BELLMAN-FORD ALGORITHM
Purpose: Finds shortest paths from a source vertex in graphs that may have negative
weights, and can detect negative-weight cycles.
Steps:
1. Initialize distances: source = 0, others = ∞.
2. Relax all edges: for each edge (u, v) with weight w, if dist[u] + w < dist[v],
update dist[v].
3. Repeat step 2 for V-1 iterations (all vertices - 1).
4. Check for negative cycles: if any edge can still be relaxed in the V-th iteration, a
negative cycle exists.
Time Complexity: O(V·E).

Bellman-Ford C Programming Implementation


3. FLOYD-WARSHALL ALGORITHM
Purpose: Finds shortest paths between all pairs of vertices in a graph, works with
negative weights (no negative cycles).
Steps:
1. Initialize a distance matrix: direct edge weights, ∞ for no edge, 0 for diagonal.
2. For each intermediate vertex k, for each pair (i, j), update:
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]).
3. Repeat for all k from 0 to V-1.
Time Complexity: O(V³).

Floyd-Warshall C Programming Implementation

You might also like