外貨換算のアルト（Android/Java /擬似コード）

Question

交換通貨問題の解決策を見つけるのに問題があります。私は、すべてのケースに対して、あらゆる洗練された高速ソリューションでこれを考えていました。

声明：私たちは、のようないくつかの為替為替レートを持っている

... USDへ

• EUR - CADへ> 0.7
• MEX - - AUDへ> 1.37
• USD> 1.8 YENへ
• LIB - > 2.3
• （.....）

このレートは現実的ではなく、1日に1回変更することができます。料金の数は、通貨が世界にあるほど大きくなる可能性があります（約150）。

（私たちができる場合）為替通貨のレートを与えられた私たちは別のものに任意の通貨からお金の量を変換するように求めていると我々は答えを与える必要があります。あなたは中間の交換率に多くの時間をジャンプしなければならない最悪の場合には、直接的である（リストに表示されます）を交換した場合

最良の場合

です。

注：ユーロから米ドルに換算すると、ユーロからユーロを逆数とみなすことができます。

私は問題がはっきりしていることを願っています。

Answer 1

各頂点に通貨名を付けた加重有向グラフを作成します。通貨AからBへのレートがある場合は、為替レートをウェイトとしてエッジ（A、B）を追加します。

を使用する（A、B）エッジではなく、（B、A）エッジがある場合（A、B）の重量で割った重量1（B、A）エッジを追加します。

D'sの頂点Cの頂点から最小重み経路を見つけるための最短パスアルゴリズムを適用し、Dに通貨Cを変換します。そのようなパスがない場合、変換は実行できません。 directed graph with non-negative weightsを参照してください。

============================================== =========================================

これは、必ずしもではないでしょうレートが倍増するので、最高の為替レートを見つける。エッジウェイトとしての交換レートの対数を使用し、負のエッジウェイトを処理できる最短パスアルゴリズムを使用することによって最良のレートを見つけることができます。

私はパトリシアと大幅に同意するだろう体重1

Answer 2

を直接交換に一致する各エッジを与える、最も少ない取引所との交流のパスを検索します。しかし、この問題は確実に裁定取引を回避することと確かに関係しています。したがって、通貨Aから通貨Bまでの「最短経路」（最低コスト）に至ります。最短経路アルゴリズムは十分に研究され、文書化されています。コルモンの中でそれらを見て、腹を立ててください。