单源最短路径代码,Java代码库,德仔网

代码语言

代码分类

【Java】单源最短路径

作者:racoon / 发布于2011/10/26/ 758

<div>/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
package singlesourcesp;
/**
*
* @author racoon
*/
public class SingleSourceSP {</div>
<div> /**
 * @param args the command line arguments
 */
 public static void main(String[] args) {
 // TODO code application logic here
 boolean goon = true;
 int [][] c = new int[11][11]; //数组维数都可以动态控制，加入个输入即可，这次只是为做作业，图快
 int [] cost = new int[11];
 int [] d = new int[11];
 int costc = 9999;
 for (int i = 0; i <= 10; i++) { //初始化数组c[][]
 for (int j = 0; j <= 10; j++) {
 c[i][j]=9999;
 }
 } 
 for (int i = 10; i >= 0; i--) { //初始化数组cost[] d[]
 cost[i]=0;
 d[i]=9999;
 }
 c[1][2]=3;c[1][3]=8;c[1][4]=5; //手动输入可达路径和权重，可以动态输入，这里图方便
 c[2][5]=13;c[2][6]=3;
 c[3][5]=6;c[3][7]=5;
 c[4][6]=7;c[4][7]=4;
 c[5][8]=4;c[5][9]=2;
 c[6][8]=3;c[6][9]=3;
 c[7][9]=8;
 c[8][10]=7;
 c[9][10]=9; 
 for (int i = 10; i >1; i--) { //寻找最短路径
 for (int j = 9; j >0; j--) {
 if (c[j][i]!=9999) {
 //System.out.println("c["+j+"]"+"["+i+"]="+c[j][i]);
 int m = c[j][i]+cost[i];
 if(m == costc)
 {
 System.out.println("可能存在两条权重相同的路径！");
 //相同处理尚未实现，暂时忽略
 }
 if (m < costc) {
 costc = m;
 d[j]=i;
 //System.out.println("d["+j+"]="+i);
 }
 
 } 
 }
 costc = 9999;
 }
 costc = 0;
 System.out.print("从1到10的最短路径为："); //输出结果
 for (int j = 1;j!=10;) {
 int n = d[j];
 costc +=c[j][n]; 
 System.out.print(j+"->");
 j=n;
 
 }
 System.out.println(10);
 System.out.println("权重为"+costc);
 }
}
</div>

试试其它关键字

　最短路径　

同语言下

可能有用的

racoon贡献的其它代码(2)