Ex4_21 最短路径算法可以应用于货币交易领域…_第十二次作业

(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();
     }
 }