Graph

How does it work?

The graph shown above is a standard bipartite graph, which is a graph containing two self-disjoint graphs (which can be thought as primitive DSUs). By applying Hungarian Algorithm on this system, we are enabled to calculate the most optimal approach of connecting nodes (or vertices) with as few edges as possible, each node having only one edge connected to others. Note that this algorithm does not yield errors should it fail to find any optimal solutions, which results in an incomplete matching.

Shortest Path Problem

Current Step: Set Obstacles | Current Algo: A* | Total Visited:: 0

A* Algorithm

A* algorithm's main difference from traditional BFS flooding method involves an informed search algorithm, whose information largely depends on the non-topological properties of a graph, restricting it from being generalized further. Despite this drawback, A* compensates it with a large leap of performance compared to traditional flooding and djikstra algorithm. The priority value for each node (less is better) is the sum of a heuristic function and the minimum distance from djikstra algorithm.