search

jacky860226 / general-graph-weighted-match-slides

一般圖最大權匹配
https://jacky860226.github.io/general-graph-weighted-match-slides/
MIT License
10 stars 0 forks source link

Hi, may I ask you about another algorithm for general-graph-weighted-matching? #1

Open RuHua93 opened 7 years ago

RuHua93 commented 7 years ago

The main idea of the algorithm: Start form any match. 1.Trying to find a path that could make the match larger by reversing the path. 2.If a path is found, reverse it, then goto 1. 3.Shuffle the nodes(why?), then goto 1 (this step could be executed at most 3 times). I wonder why this algorithm works?(In fact, it seems work well) I'm really puzzled. Here is the code: http://www.cnblogs.com/wmzisfoolish/p/5639893.html Any reply is appreciated :-)

jacky860226 commented 7 years ago

You can see this paper:

Blossom V: A new implementation of a minimum cost perfect matching algorithm