动态规划：多段图最短路径_无若呓语

http://blog.sina.com.cn/u/1307520317

首页博文目录关于我

个人资料

无若呓语

微博

加好友发纸条

写留言加关注

博客等级：
博客积分：0

博客访问：2,429
关注人气：14
获赠金笔：0支
赠出金笔：0支
荣誉徽章：

正文字体大小：大中小

动态规划：多段图最短路径

(2008-10-14 20:32:04)

标签：

动态

规划：多段图

最短

路径

it

分类：数据结构&算法设计与分析

动态规划：多段图最短路径

cost[8]=C89+cost[9]=3 path[8]=9

cost[7]=C79+cost[9]=7 path[8]=9

cost[6]=min{C68+cost[8]}=8 path[6]=8

cost[5]=min{C57+cost[7],C58+cost[8]}=9 path[5]=8

8+7 , 6+3

cost[4]=min{C47+cost[7],C48+cost[8]}=9 path[4]=8

5+7 ,6+3

cost[3]=min{C35+cost[5],C36+cost[6]}=13 path[3]=5

cost[2]=min{C23+cost[3],C24+cost[4],C26+cost[6]}=14 path[2]=3

cost[1]=min{C14+cost[4],C15+cost[5]}=17 path[1]=5

cost[0]=min{C01+cost[1],C02+cost[2]}=15 path[0]=2

path[0]=2

path[2]=3

path[3]=5

path[5]=8

path[8]=9

最短路径为：0-2-3-5-8-9

---以下代码使用的是Java语言（Java写的顺手了o(∩_∩)o...）

//多段图求最短路径
class Cost{
        int C=0;
        int costId=0;
        public Cost(){}
        public Cost(int C,int costC,int id){
                this.C=C+costC;
                this.costId=id;
        }
}

public class Graphic {
        static int node[][]={
                   //0,1,2,3,4,5,6,7,8,9
                        {0,4,1,0,0,0,0,0,0,0},
                        {0,0,0,0,9,8,0,0,0,0},
                        {0,0,0,1,0,7,8,0,0,0},
                        {0,0,0,0,0,4,7,0,0,0},
                        {0,0,0,0,0,0,0,5,6,0},
                        {0,0,0,0,0,0,0,8,6,0},
                        {0,0,0,0,0,0,0,0,5,0},
                        {0,0,0,0,0,0,0,0,0,7},
                        {0,0,0,0,0,0,0,0,0,3},
                        {0,0,0,0,0,0,0,0,0,0}
        };
        static Cost [] cost=new Cost[10];
        static Cost [] dis=new Cost[10];
        static int [] path=new int[10];
        public static int C(int a,int b){
                return node[a][b];
        }//
        public static void show(){
                for(int i=0;i<node.length;i++){
                        for(int j=0;j<node[i].length;j++){
                                System.out.print(node[i][j]+" ");
                        }
                        System.out.println();
                }
        }//
        public static void initCost(){
                for(int i=0;i<cost.length;i++){
                cost[i]=new Cost();
        }
        }//
        public static void initDis(){
                for(int i=0;i<dis.length;i++){
                dis[i]=new Cost();
        }
        }//
        public static int plength(Cost dis[]){
                int num=0;
                for(int i=0;i<dis.length;i++){
                        if(dis[i].C==0){
                                num=i;
                                break;
                        }
                }
                return num;
        }
        public static int plength(int dis[]){
                int num=0;
                for(int i=0;i<dis.length;i++){
                        if(dis[i]==0){
                                num=i;
                                break;
                        }
                }
                return num;
        }
        public static Cost min(Cost dis[],int length){//取最小值
                Cost m=new Cost();
                m.C=9999;
                for(int i=0;i<length;i++){
                   if(dis[i].C<m.C){
                           m.C=dis[i].C;
                           m.costId=dis[i].costId;
                   }
                }
                return m;
        }//
        
        public static int[] goPoints(int start){//返回可到达哪些点
                int [] p={0,0,0,0,0,0,0,0,0,0};
                int counter=0;
                for(int y=0;y<node[start].length;y++){
                           if(node[start][y]!=0){
                                  p[counter]=y;
                                  counter++;
                       }
                }
                return p;
        }//
        ////////////////////////////////////////////////////////////////////////
        public static void process(){//核心算法
                initCost();
                for(int i=8;i>=0;i--){
                initDis();
                        for(int j=0;j<plength(goPoints(i));j++){  
                                int [] p=goPoints(i);
                dis[j]=new Cost(C(i,p[j]),cost[p[j]].C,p[j]);
                        }
        //
        cost[i]=min(dis,plength(dis));
        path[i]=cost[i].costId;
                }
        }//
        public static void output(){//输出 距离 及 路径
                System.out.println("0-9最短距离为："+cost[0].C);
                System.out.println("路径如下：");
                int t=path[0];
                System.out.print("0"+"-");
                do{
                        System.out.print(t+"-");
                        t=path[t];
                }while(t<9);
                System.out.print("9");
        }
        ////////////////////////////////////////////////////////////////////////
        public static void main(String[] args){
                show();
                process();
                for(int i=0;i<cost.length;i++){
                System.out.println("cost"+i+":"+cost[i].C+"   "+"path"+i+":"+path[i]);
        }
                output();
      
        }

}

阅读┊ 收藏 ┊ 喜欢 ▼ ┊打印┊举报/Report

前一篇：一个EXTJS与JSP连接把数据写入数据库的例子

后一篇：贪心法解硬币问题

新浪BLOG意见反馈留言板　欢迎批评指正