Scribd
Upload
12 views2 pages

Algorithm Descriptions

The document describes various algorithms including Floyd-Warshall for shortest paths in graphs, Bellman-Ford for single-source shortest paths with negative weights, and backtracking algorithms for the N-Queens problem. It also covers dynamic programming for the 0/1 Knapsack and Travelling Salesman problems, as well as graph coloring and search algorithms like Least Cost Search, BFS, and DFS. Each algorithm is briefly explained in terms of its purpose and methodology.

Uploaded by

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

Algorithm Descriptions

The document describes various algorithms including Floyd-Warshall for shortest paths in graphs, Bellman-Ford for single-source shortest paths with negative weights, and backtracking algorithms for the N-Queens problem. It also covers dynamic programming for the 0/1 Knapsack and Travelling Salesman problems, as well as graph coloring and search algorithms like Least Cost Search, BFS, and DFS. Each algorithm is briefly explained in terms of its purpose and methodology.

Uploaded by

chintalwarjanhavi
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 2

Algorithm Descriptions in Words

1. Floyd-Warshall Algorithm
This algorithm finds the shortest distances between all pairs of vertices in a weighted graph.
It works by checking if a path from vertex i to vertex j through vertex k is shorter than the
current known path. It updates the distance matrix in-place for every pair (i, j) using every
possible intermediate vertex k.

2. Bellman-Ford Algorithm
Used to find the shortest paths from a single source to all vertices in a graph, even with
negative weights. It relaxes all edges repeatedly (V-1 times) and updates the shortest path.
After all iterations, it checks for negative weight cycles.

3. N-Queens (4 or 8 Queens) Problem


This is a backtracking algorithm to place N queens on an N×N chessboard such that no two
queens attack each other. It tries placing a queen in each row and backtracks if a conflict
occurs with existing queens.

4. 0/1 Knapsack Problem


It’s a dynamic programming algorithm used to maximize the total value in a knapsack of
limited weight capacity. Each item can either be included or excluded. The solution builds a
table to decide the maximum value at each weight limit for subsets of items.

5. Travelling Salesman Problem (TSP)


This problem aims to find the shortest possible route that visits every city once and returns
to the origin city. Using dynamic programming and bit masking, it keeps track of the
shortest route visiting a combination of cities.

6. Graph Coloring
Graph coloring assigns colors to vertices so that no two adjacent vertices share the same
color. The algorithm tries different colors for each vertex using backtracking and checks for
valid assignments.
7. Least Cost Search (Uniform Cost Search)
This search expands the node with the least path cost first. It uses a priority queue to keep
track of the lowest-cost path to each node, ensuring the optimal path is found in weighted
graphs.

8. Breadth-First Search (BFS)


BFS explores all vertices of a graph layer by layer starting from a source vertex. It uses a
queue and visits all neighbors of the current node before going deeper.

9. Depth-First Search (DFS)


DFS explores a graph by going as deep as possible along each branch before backtracking. It
uses recursion or a stack to remember the path and visits.

You might also like