For a given weighted graph $G = (V, E)$, there is a simple algorithm for finding the minimum weight circuit by running [Dijkstra's algorithm](https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm#Applications) $|E|$ times.


Also for a matroid $M = (E, I)$ one can use the greedy Rado-Edmonds algorithm to find a basis of minimum weight.


I'm interested whether an algorithm for all weighted binary matroids, not just weighted graphic matroids, exists? Specifically an algorithm polynomial on the size of the ground set, using the independence oracle model?



Algorithm for finding a minimum weight circuit in a weighted binary matroid
The problem is NP-hard (even in the unweighted case) via a well-known connection to coding theory. Namely, if $A$ is the parity check matrix of a binary linear code $C$, then the distance of $C$ is the size of a shortest circuit in the binary matroid represented by $A$. In [The intractability of computing the minimum distance of a code](https://ieeexplore.ieee.org/document/641542), Vardy proved that computing the distance of a binary linear code is NP-hard.


However, for proper minor-closed classes of binary matroids, Geelen, Gerards, and Whittle conjecture that the problem is solvable in polynomial-time. See the paper [Computing girth and cogirth in perturbed graphic matroids](https://arxiv.org/abs/1504.07647) or [Finding Shortest Circuits in Binary Matroids](http://matroidunion.org/?p=1106) on the Matroid Union Blog for more information.


