Dijkstra’s Algorithm

Given a network of cities and the distances between them,the task is to find the shortest path from a city(source) to all other cities connected to it.The network of cities with their distances is represented as a weighted digraph.It is also known as single-source,shortest path problem. Algorithm- N is the number of vertices labeled {0,1,2,3….N-1} […]

Continue reading →

Prims Algorithm

Let G=(V,E) be an undirected,connected and weighted graph.A sub-graph T=(V,E’) of G is a spanning tree of G if T is a tree.There may be several spanning trees that may be extracted from it.A spanning tree has N vertices and N-1 edges.This is because of the property of trees.A minimum cost spanning tree is a […]

Continue reading →

BFS & DFS

A traversal is a systematic walk which visits the nodes of the graph in a specific order. Two Types:- 1.Breadth First Traversal 2.Depth First Traversal Breadth First Traversal- It traverses the successors of the start node,generation after generation in a horizontal or linear fashion. Algorithm- BFT(s) { //s is the start vertex of the traversal […]

Continue reading →

Floyd Warshall Algorithm

The problem is to find shortest distances between every pair of vertices in a given edge weighted directed graph. The graph is represented in the form of an adjacency matrix where each cell A[i][j] represents the weight of the edge from vertex i to vertex j. If i==j,then A[i][j]=0. If there is no edge from […]

Continue reading →