Skip to content

Latest commit

 

History

History
20 lines (18 loc) · 1.19 KB

readme.md

File metadata and controls

20 lines (18 loc) · 1.19 KB
Raw

Graph algorithms and related data structures

Programming language chosen - Python

Problem statements

Discover Single-source Shortest Path :

Find shortest path tree in both directed and undirected weighted graphs for a given source vertex. Assume there is no negative edge in your graph. You will print each path and path cost for a given source.

Trace Minimum Spanning Tree :

Given a connected, undirected, weighted graph, find a spanning tree using edges that minimizes the total weight. Use either Kruskal's or Prim's algorithm to find Minimum Spanning Tree (MST). You will printout edges of the tree and total cost of minimum spanning tree.

Finding Strongly Connected Components(SCC) :

Given a directed graph G with n vertices and m edges. Decompose this graph into Strongly Connected Components (SCCs) and print the components.

Steps

  1. Please install dependencies : Python 3, NumPy, Pandas
  2. Clone the repository
  3. Navigate to the code folder
  4. Go to root folder of the algorithm that you want to run: Example - DijikstrasShortestPath
  5. Open command prompt
  6. Run python main.py
  7. Choose input file from available options when prompted
  8. Output will be printed in console.