The Hungarian algorithm allows a "minimum matching" to be found. This can be used in instances where there are multiple quotes for a group of activities and each activity must be done by a different person, to find the minimum cost to complete all of the activities.

Steps

  1. 1
  2. 2
    Advertisement
  3. 3
  4. 4
  5. 5
  6. 6
  7. 7
  8. 8
  9. 9
  10. 10
  11. Advertisement

Community Q&A

  • Question
    How do the Dijkstra and Floyd algorithms differ?
    Community Answer
    Community Answer
    You can use the Dijkstra algorithm to compute the shortest path from the source node to any other node. You can use the Floyd-Warshall algorithm to compute the shortest path from any node to any node. Don't use Dijkstra if there are arcs with negative weight. If there is a negative cycle in your graph, you cannot use a polynomial algorithm.
  • Question
    How is the Hungarian method applied for obtaining a solution if the matrix is a rectangle?
    Community Answer
    Community Answer
    You would first add "dummy" row(s) or column(s) to make it square, with the "dummy" value being the highest value from that column or row, respectively.
  • Question
    Can the column reduction be done first and row reduction second?
    Community Answer
    Community Answer
    Yes, it does not matter which reduction you do first. Doing row reduction first will give you a different final matrix, but the optimal solution obtained from that matrix will be the same as you get by doing the column reduction first. Furthermore, doing the row reduction first can sometimes reduce the number of steps required to get the optimal solution.
Advertisement

Things You'll Need

  • Paper
  • Pen/pencil


About This Article

wikiHow is a “wiki,” similar to Wikipedia, which means that many of our articles are co-written by multiple authors. To create this article, 10 people, some anonymous, worked to edit and improve it over time. This article has been viewed 297,265 times.
98 votes - 81%
Co-authors: 10
Updated: January 3, 2022
Views: 297,265
Advertisement