import?java.util.Scanner;

public?class?Test4?{
	final?static?int?MAX_VERTECX_NUM?=?20;
	final?static?int?INT_MIN?=?0;

	static?int[][]?Path?=?new?int[MAX_VERTECX_NUM][MAX_VERTECX_NUM];//用來記錄套匯過程中要經(jīng)過的路徑
	static?float[][]?value?=?new?float[MAX_VERTECX_NUM][MAX_VERTECX_NUM];//用來記錄經(jīng)過討回操作后得到的值

	/**
	?*?套匯問題
	?*/
	public?static?void?main（String[]?args）?{
		//?TODO?Auto-generated?method?stub

		int?i?flag?=?0;
		MGraph?G?=?new?MGraph（）;
		CreateDG（G）;
		ShortestPath_FLOYD（G）;
		//在輸出兌換序列時(shí)采用了遞歸算法：這個(gè)算法逆序輸出了兌換序列
		for?（i?=?1;?i?<=?G.vexnum;?i++）?{
			if?（value[i][i]?>?1）?{
				System.out.println（“兌換結(jié)果為：“?+?value[i][i]）;
				if?（Path[i][i]?!=?0）
					System.out.println（i?+?“?“?+?i）;
				System.out.print（“兌換順序的逆序輸出：“?+?i?+?“?“）;
				Procedure_print（i?i）;//遞歸，貨幣i至j中間頂點(diǎn)
				System.out.println（）;
				flag?=?1;
			}
		}
		if?（flag?==?0）
			System.out.println（“不存在套匯路線！“）;

	}

	static?void?CreateDG（MGraph?G）?{
		int?i?j?=?0?k;
		float?w?=?0;
		System.out.print（“請輸入節(jié)點(diǎn)和弧度：“）;
		Scanner?sc?=?new?Scanner（System.in）;
		G.vexnum?=?sc.nextInt（）;
		G.arcnum?=?sc.nextInt（）;
		System.out.println（“G->vexnum=“?+?G.vexnum?+?““?+?“G->arcnum=“
				+?G.arcnum）;
		for?（i?=?1;?i?<=?G.vexnum;?i++）?{
			G.vexs[i]?=?i;
		}
		for?（i?=?1;?i?<=?G.vexnum;?i++）?{
			for?（j?=?1;?j?<=?G.vexnum;?j++）?{
				G.arc[i][j]?=?INT_MIN;
			}
		}
		System.out.println（“請輸入矩陣：“）;
		sc?=?new?Scanner（System.in）;
		for?（k?=?1;?k?<=?G.arcnum;?k++）?{
			String?str?=?sc.next（）;
			i?=?Integer.parseInt（str.split（““）[0]）;
			j?=?Integer.parseInt（str.split（““）[1]）;
			w?=?Float.parseFloat（str.split（““）[2]）;
			G.arc[i][j]?=?w;
		}

	}

	static?void?ShortestPath_FLOYD（MGraph?G）?{
		int?i?j?k;
		for?（i?=?1;?i?<=?G.vexnum;?i++）?{
			for?（j?=?1;?j?<=?G.vexnum;?j++）?{
				if?（i?==?j）
					value[i][j]?=?1;
				else
					value[i][j]?=?G.arc[i][j];
				if?（G.arc[i][j]?>?INT_MIN）
					Path[i][j]?=?i;
				else
					Path[i][j]?=?0;
			}
		}
		//算法中的關(guān)鍵步驟：
		for?（k?=?1;?k?<=?G.vexnum;?k++）?{
			for?（i?=?1;?i?<=?G.vexnum;?i++）?{
				for?（j?=?1;?j?<=?G.vexnum;?j++）?{
					if?（!（i?==?j?&&?j?==?k））?{
						if?（value[i][k]?*?value[k][j]?>?value[i][j]）?{//這里判斷是否使兌換率增大，如果增大則記錄下來
							value[i][j]?=?value[i][k]?*?value[k][j];
							Path[i][j]?=?Path[k][j];
						}
					}
				}
			}

		}
	}

	static?void?Procedure_print（int?i?int?j）?{
		if?（Path[i][j]?==?i）?{
			System.out.println（i）;
			return;
		}?else?{
			System.out.print（Path[i][j]+“?“）;
			Procedure_print（i?Path[i][j]）;
		}
	}

}

class?MGraph?{
	final?static?int?MAX_VERTECX_NUM?=?20;
	final?static?int?INT_MIN?=?0;

	static?int[][]?Path?=?new?int[MAX_VERTECX_NUM][MAX_VERTECX_NUM];
	static?float[][]?value?=?new?float[MAX_VERTECX_NUM][MAX_VERTECX_NUM];
	int[]?vexs?=?new?int[MAX_VERTECX_NUM];?//?頂點(diǎn)向量?可以存儲(chǔ)每個(gè)頂點(diǎn)的信息
	float[][]?arc?=?new?float[MAX_VERTECX_NUM][MAX_VERTECX_NUM];//?鄰接矩陣
																//?主要存放關(guān)于邊的信息
	int?vexnum?arcnum;?//?圖中當(dāng)前頂點(diǎn)數(shù)和弧數(shù)
}

?屬性????????????大小?????日期????時(shí)間???名稱
-----------?---------??----------?-----??----
?????目錄???????????0??2012-11-27?12:58??java算法分析與設(shè)計(jì)之套匯問題源代碼和實(shí)驗(yàn)報(bào)告\
?????目錄???????????0??2012-11-27?12:58??java算法分析與設(shè)計(jì)之套匯問題源代碼和實(shí)驗(yàn)報(bào)告\04\
?????文件?????????232??2012-11-16?12:32??java算法分析與設(shè)計(jì)之套匯問題源代碼和實(shí)驗(yàn)報(bào)告\04\.classpath
?????文件?????????378??2012-11-19?12:59??java算法分析與設(shè)計(jì)之套匯問題源代碼和實(shí)驗(yàn)報(bào)告\04\.project
?????目錄???????????0??2012-11-27?12:58??java算法分析與設(shè)計(jì)之套匯問題源代碼和實(shí)驗(yàn)報(bào)告\04\bin\
?????文件?????????609??2012-11-19?17:48??java算法分析與設(shè)計(jì)之套匯問題源代碼和實(shí)驗(yàn)報(bào)告\04\bin\MGraph.class
?????文件????????3326??2012-11-19?17:48??java算法分析與設(shè)計(jì)之套匯問題源代碼和實(shí)驗(yàn)報(bào)告\04\bin\Test4.class
?????目錄???????????0??2012-11-27?12:58??java算法分析與設(shè)計(jì)之套匯問題源代碼和實(shí)驗(yàn)報(bào)告\04\src\
?????文件????????3178??2012-11-21?13:30??java算法分析與設(shè)計(jì)之套匯問題源代碼和實(shí)驗(yàn)報(bào)告\04\src\Test4.java
?????文件???????83721??2012-11-21?19:58??java算法分析與設(shè)計(jì)之套匯問題源代碼和實(shí)驗(yàn)報(bào)告\04.docx