python - Solution search solved using DFS or Greedy BFS? -

i have problem sounds this: company has 4 taxis in 4 different (a b c d) locations. 4 people (w x y z) call company need taxi. need find fastest way taxis can arrive @ people knowing taxi can go 1 person , each taxi has assigned value between destination , people's destinations.

i thinking of building tree possible combinations ex: aw-bx-cy-dz or ax-bw-cy-dz etc , find minimum cost each of them need solve using dfs or greedy bfs approach. ideas how work? can't imagine it.

i want idea on how solve using dfs/gbfs. can't figure out how have go or when search end since i'm looking minimum distance used

this instance of assignment problem, finding maximum/minimum weight matching in weighted bipartite graph. common algorithm used solve kind of problem hungarian algorithm, solving in o(n^3). there python module implementing - munkres.

however, if want use dfs/bfs can think of naive algorithm creating every possible solution, , searching through solution space using dfs/bfs, highly nonoptimal.