Skip to content

Minimize the cost of building the connected highways by using graph theory and priority queue. The connected highways cannot be an acyclic or cycle.

Notifications You must be signed in to change notification settings

atomb0mb/TransportationManager

Repository files navigation

This project involves

  1. Vertex/Vertices
  2. Edge/Edges
  3. Adjacent list
  4. Disjoint-set/Union
  5. Heaps/Priority Queues
  6. Acyclic undirected graph
  7. Kruskal algorithm

Steps to find the minimum cost of connected highway (From Destination A to Destination B)

  1. Find all weighted edges (Find all vertices and caculate the weighted edge)
  2. Store all weighted edges Priority Queues (Minimum spanning tree)
  3. Dequeue the Priority Queues (The first will be the smallest or cheapest connection)
  4. Unions or subset the edges that did not have similar parent vertex or node. (To avoid cycle)
  5. Repeat untill the edges are connected to from destination A to destination B.

About

Minimize the cost of building the connected highways by using graph theory and priority queue. The connected highways cannot be an acyclic or cycle.

Topics

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages