waysun一路陽光

          不輕易服輸,不輕言放棄.--心是夢的舞臺,心有多大,舞臺有多大。踏踏實實做事,認認真真做人。

            BlogJava :: 首頁 :: 新隨筆 :: 聯(lián)系 ::  :: 管理 ::
            167 隨筆 :: 1 文章 :: 64 評論 :: 0 Trackbacks

          來源:http://blog.chinaunix.net/u1/50399/showart_408864.html

          /*
           * @title:關鍵路徑
           * @input: 有向帶權圖,圖以鄰接表形式表示,頭結點只存儲該頂點的度,后繼結點存儲頂點及權值
           * @output: 所有可能關鍵路徑的并集path,path[i][0]及path[i][1]代表邊的頂點,path[i][2]代表權值
           */

          import java.util.*;
          public class CriticalPathTest
          {  
             public static void main(String[] args)
             {
                 int[][] graph={{0, 1,6, 2,4, 3,5,},{1, 4,1,},{1, 4,1},{1, 5,2,},
                 {2, 6,9, 7,7,},{1, 7,4,},{1, 8,2,},{2, 8,4,},{2,},};
                 int[][] path;

                 CriticalPath criticalPath=new CriticalPath();
                 criticalPath.input(graph);
                 path=criticalPath.getPath();
                 for(int i=0; i<criticalPath.getLength(); i++){
                     System.out.println("邊:" + path[i][0]+ "-" + path[i][1] +" 權:"+ path[i][2]);
                 }
             }
          }

          class CriticalPath
          {
              private int[][] graph;
              private int[][] path;
              int len;
              
              void input(int[][] graph)
              {
                  this.graph=graph;
                  path=new int[graph.length-1][];
                  len=0;
                  calculate();
              }

              void calculate()
              {
                  int[] ve=new int[graph.length];  //事件的最發(fā)生時間
                  Stack stack1=new Stack();
                  Stack stack2=new Stack();
                  int i,j,v;
                  for(int t : ve) t=0;
                  stack1.push(0);
                  while(stack1.empty()!=true){
                      v=(Integer)stack1.pop();
                      for(i=1; i<graph[v].length; i=i+2){
                          j=graph[v][i];
                          if((--graph[j][0])==0){
                              stack1.push(j);
                          }
                          if(ve[v]+graph[v][i+1]>ve[j]){
                              ve[j]=ve[v]+graph[v][i+1];
                          }
                      }
                      stack2.push(v);
                  }

                  int[] vl=new int[graph.length];  //事件的最遲生時間
                  for(i=0; i<graph.length; i++) vl[i]=1000;
                  vl[graph.length-1]=ve[graph.length-1];
                  while(stack2.empty()!=true){
                      v=(Integer)stack2.pop();
                      for(i=1; i<graph[v].length; i=i+2){
                          j=graph[v][i];
                          if(vl[j]-graph[v][i+1]<vl[v]){
                              vl[v]=vl[j]-graph[v][i+1];
                          }
                      }
                  }

                  for(v=0; v<graph.length-1; v++){ //求關鍵路徑的所有邊
                      for(i=1; i<graph[v].length; i=i+2){
                          j=graph[v][i];
                          if(ve[v]==(vl[j]-graph[v][i+1])){
                              int[][] p={{v, j,graph[v][i+1],},};
                              path[len++]=p[0];
                          }
                      }
                  }
              }
              
              int[][] getPath()
              {
                  return path;
              }
              
              int getLength()
              {
                  return len;
              }
          }

          結果如下:

          邊:0-1 權:6
          邊:1-4 權:1
          邊:4-6 權:9
          邊:4-7 權:7
          邊:6-8 權:2
          邊:7-8 權:4

          易知關鍵路徑有兩條:

          0-1-4-6-8 及 0-1-4-7-8

          posted on 2009-04-15 22:22 weesun一米陽光 閱讀(550) 評論(0)  編輯  收藏 所屬分類: JAVA源碼 、總結備用
          主站蜘蛛池模板: 涡阳县| 巩留县| 新民市| 秦安县| 寻乌县| 奉化市| 永康市| 长兴县| 贵溪市| 招远市| 大洼县| 沁水县| 旬阳县| 丹棱县| 沛县| 洛隆县| 南部县| 沾化县| 彰化县| 潮州市| 介休市| 东安县| 行唐县| 武平县| 太白县| 游戏| 淮北市| 林州市| 永德县| 延边| 静乐县| 赣州市| 三明市| 岳西县| 涡阳县| 阿拉善盟| 饶平县| 安顺市| 芦山县| 封丘县| 丰城市|