(a) 建立一个有向图G(V,E)，每个顶点表示一种货币，两个顶点之间的边权的大小ex[u][v]表示两种货币之间的汇率，若要找一个最有利的兑换序列，把货币s兑换成货币t，即在若干种兑换序列中选择一条合适的兑换序列，将等量货币s尽可能多的兑换货币t，令money[x]表示一个s币可以兑换多少个x币。初始时令money[s]=1,money[x]=0.利用bellman-ford算法，修改算法中的update过程如下
do for each edge (u, v) ∈ E[G]
if(money[v]<money[u]*ex[u][v])
money[v]=money[u]*ex[u][v]
如果不存在异常情形，则兑换的最长路径最多有n-1条边(n为货币的种数).
(b) 若存在异常情形，则在求得最多n-1条边的基础上再进行依次update操作，某个顶点的money一定增加。
package org.xiu68.ch04.ex12;
public class Ex4_21 {
public static void main(String[] args) {
// TODO Auto-generated method stub
double max=10000000;
double[][] edges=new double[][]{
{1,10,5,3},
{0.05,1,0,5},
{0.1,0,1,2},
{0.01,0.15,0.1,1}
};
MGraph1 m1=new MGraph1(edges);
m1.bellmanFord(0, 3);
//输出
/*
1个第0种货币最多可以兑换50.0个第3种货币
不存在异常情况
*/
double[][] edges1=new double[][]{
{1,10,5,3},
{0.05,1,0,5},
{0.1,0,1,2},
{0.2,0.15,0.1,1}
};
MGraph1 m2=new MGraph1(edges1);
m2.bellmanFord(0, 3);
//输出
/*
1个第0种货币最多可以兑换5000.0个第3种货币
存在异常情况
*/
}
}
class MGraph1{
private double[][] edges; //有向图边集
private int vexNum; //顶点数目
private double[] money; //money[i]表示用一个s币可以兑换多少i币
public MGraph1(double[][] edges){
this.edges=edges;
this.vexNum=edges.length;
this.money=new double[vexNum];
}
public void bellmanFord(int s,int t){
//初始化money数组
for(int i=0;i<vexNum;i++){
money[i]=0;
}
money[s]=1;
for(int i=1;i<vexNum;i++){ //从源点到任何一个顶点最多有vexNum条边的最短路径
boolean flag=false; //记录在本次循环中从源点到某个顶点是否有更短的路径
//遍历所有的边
for(int j=0;j<vexNum;j++){
for(int k=0;k<vexNum;k++){
if(edges[j][k]!=0 && money[k]<money[j]*edges[j][k]){
money[k]=money[j]*edges[j][k];
flag=true;
}
}
}
if(flag==false) //已经求得所有顶点最多edgeNum条边的最短路径
break;
}
System.out.println("1个第"+s+"种货币最多可以兑换"+money[t]+"个第"+t+"种货币");
boolean flag=false;
for(int i=0;i<vexNum;i++){
for(int j=0;j<vexNum;j++){
if(Math.abs(edges[i][j])!=0 && money[j]<money[i]*edges[i][j]){
flag=true;
}
}
}
if(flag==false)
System.out.println("不存在异常情况");
else
System.out.println("存在异常情况");
System.out.println();
}
}