關鍵路徑演算法java實現（什麼情況下需要使用關鍵路徑演算法）

本文目錄一覽：

• 1、java關鍵字查詢演算法
• 2、關鍵路徑怎麼算
• 3、JAVA問題求解求速度 http://zhidao.baidu.com/question/206204688.html
• 4、圖的關鍵路徑
• 5、關鍵路徑怎麼求？求詳解。
• 6、一個簡單的演算法演示程序(JAVA語言實現)

java關鍵字查詢演算法

import java.io.FileReader;

import java.io.BufferedReader;

import java.io.File;

public class search

{

//查找方法，參數，文件絕對路徑，查找關鍵字

public static boolean search(String filepath,String key)

{

try

{

File f = new File(filepath);

FileReader fr = new FileReader(f);

BufferedReader br = new BufferedReader(fr);

String s = “”;

//int i = 1;

while((s = br.readLine()) != null)

{

if(s.indexOf(key) != -1)

{

return true;

}

}

return false;

}

catch(Exception e)

{

e.printStackTrace();

return false;

}

}

public static void main(String args[])

{

System.out.println(search.search(“d://t.txt”,”l2″));

}

}

修改了下，加兩個變數，可以指出查找的位置。

import java.io.FileReader;

import java.io.BufferedReader;

import java.io.File;

public class search

{

//查找方法，參數，文件絕對路徑，查找關鍵字

public static String search(String filepath,String key)

{

try

{

File f = new File(filepath);

FileReader fr = new FileReader(f);

BufferedReader br = new BufferedReader(fr);

String s = “”;

int i = 1;

int m = 0;

while((s = br.readLine()) != null)

{

if((m = s.indexOf(key)) != -1)

{

return “第”+i+”段,第”+m+”處”;

}

i++;

}

return null;

}

catch(Exception e)

{

e.printStackTrace();

return null;

}

}

public static void main(String args[])

{

System.out.println(search.search(“d://t.txt”,”asd”));

}

}

這個，查漢字是沒有問題的。

另外，你要全文檢索的話，indexOf（）還有個方法，indexOf(int start,String key),指定開始查找的位置跟關鍵字，你查到一處後，將這個數值加1，做為繼續查找的開始位置就可以了。

關鍵路徑怎麼算

輸入e條弧j，k，建立AOE網的存儲結構；從源點v1出發，令ve(1)=0，求 ve(j)，2=j=n；從匯點vn出發，令vl(n)=ve(n)，求 vl(i)，1=i=n-1。

根據各頂點的ve和vl值，求每條弧s（活動）的最早開始時間e(s)和最晚開始時間l(s)，其中e(s)=l(s)的為關鍵活動。

求關鍵路徑必須在拓撲排序的前提下進行，有環圖不能求關鍵路徑；只有縮短關鍵活動的工期才有可能縮短工期；若一個關鍵活動不在所有的關鍵路徑上，減少它並不能減少工期；只有在不改變關鍵路徑的前提下，縮短關鍵活動才能縮短整個工期。

擴展資料

在項目管理中，編製網路計劃的基本思想就是在一個龐大的網路圖中找出關鍵路徑，並對各關鍵活動，優先安排資源，挖掘潛力，採取相應措施，盡量壓縮需要的時間。

而對非關鍵路徑的各個活動，只要在不影響工程完工時間的條件下，抽出適當的人力、物力和財力等資源，用在關鍵路徑上，以達到縮短工程工期，合理利用資源等目的。在執行計划過程中，可以明確工作重點，對各個關鍵活動加以有效控制和調度。

關鍵路徑法主要為一種基於單點時間估計、有嚴格次序的一種網路圖。它的出現為項目提供了重要的幫助，特別是為項目及其主要活動提供了圖形化的顯示，這些量化信息為識別潛在的項目延遲風險提供極其重要的依據。

參考資料來源：百度百科-關鍵路徑法

參考資料來源：百度百科-關鍵路徑

JAVA問題求解求速度 http://zhidao.baidu.com/question/206204688.html

功能要求：

1. 選擇一個演算法（提供選擇見下），利用各種方法（圖形、動畫等）演示演算法的演示過程。

2. 可以進行手動演示，也可以自動步進式演示。

3. 允許用戶設置演算法的各個輸入參數，以及自動步進式演示中的時間間隔。

4. 不同的演算法輸入要求見下。

界面要求：

1. 盡量使用圖形界面實現，要符合日常軟體使用規範來設計菜單和界面。

2. 如果無法實現圖形界面，則在命令行方式下也需要提供菜單，方便用戶操作。

其他要求：

1. 標識符命名遵循Windows命名規範。

2. 能夠注意各種異常處理，注重提高程序運行效率。

提交內容：

1. 全部源代碼。

2. 軟體設計和使用說明書（UML類圖；實現的功能、主要技術；使用幫助文檔）

參考演算法：

1. 最小生成樹演算法：Prim演算法、Kruskal演算法。允許以下方式輸入一個圖形：繪製圖形、輸入鄰接矩陣、輸入邊及其關聯的頂點。要求在圖形方式下進行演示演算法執行步驟。

2. 單源最短路演算法：Dijkstra演算法。允許以下方式輸入一個圖形：繪製圖形、輸入鄰接矩陣、輸入邊及其關聯的頂點。要求在圖形方式下進行演示演算法執行步驟。

3. 最優編碼演算法：Huffman編碼演算法。允許用戶輸入一段英文文字，或者打開一個txt文檔（英文內容），據此文檔內容進行編碼。要求動態列出每個字元的出現概率統計結果以及對應編碼。

4. 其他可供演示的具有一定難度的演算法，如關鍵路徑問題、有向圖的極大連通分支等。

圖的關鍵路徑

關鍵概念定義

AOV網 ：在一個表示工程的有向圖中，用頂點表示活動，用弧表示活動之間的優先關係，這樣的有向圖為頂點表示活動的網，就是AOV網。

關鍵路徑演算法原理 ：先求所有頂點的事件最早發生時間（從起點開始計算），如有頂點1和頂點2都到達頂點3，那麼頂點3的最早開始時間為max(頂點1 + 路徑長度，頂點2 + 路徑長度)；之後求出所有頂點的時間最遲發生時間（從終點開始計算），如頂點3會到達頂點4和頂點5，那麼頂點3的最遲發生時間為min（頂點4 – 路徑長度，頂點5 – 路徑長度)。比較事件最早發生時間數組和事件最遲發生時間數據，若是對應位置的值相等（即沒有可延遲的時間），那麼該頂點就是關鍵路徑上的頂點。比較完所有頂點即可輸出關鍵路徑。

關鍵路徑怎麼求？求詳解。

關鍵路徑的演算法是建立在拓撲排序的基礎之上的，這個演算法中用到了拓撲排序。

1． 什麼是拓撲排序？

舉個例子先：一個軟體專業的學生學習一系列的課程，其中一些課程必須再學完它的基礎的先修課程才能開始。如：在《程序設計基礎》和《離散數學》學完之前就不能開始學習《數據結構》。這些先決條件定義了課程之間的領先(優先)關係。這個關係可以用有向圖更清楚地表示。圖中頂點表示課程，有向邊表示先決條件。若課程i是課程j的先決條件，則圖中有弧i,j。若要對這個圖中的頂點所表示的課程進行拓撲排序的話，那麼排序後得到的序列，必須是按照先後關係進行排序，具有領先關係的課程必然排在以它為基礎的課程之前，若上例中的《程序設計基礎》和《離散數學》必須排在《數據結構》之前。進行了拓撲排序之後的序列，稱之為拓撲序列。

2． 如何實現拓撲排序？

很簡單，兩個步驟：

1． 在有向圖中選一個沒有前驅的頂點且輸出。

2． 從圖中刪除該頂點和以它為尾的弧。

重複上述兩步，直至全部頂點均已輸出，或者當前圖中不存在無前驅的頂點為止。後一種情況則說明有向圖中存在環。

3． 什麼是關鍵路徑？

例子開頭仍然，圖1是一個假想的有11項活動的A0E-網。其中有9個事件v1,v2……，v9，每個事件表示在它之前的活動一完成，在它之後的活動可以開始。如v1表示整個工程的開始，v9表示整個工程結束，v5表示a4和a5已完成，a7和a8可以開始。與每個活動相聯繫的數是執行該活動所需的時間。比如，活動a1需要6天，a2需要4天。

由於整個工程只有一個開始點和一個完成點，故在正常情況(無環)下，網中只有一個入度為零的點(稱作源點)和一個出度為零的點(叫做匯點)。

那麼該工程待研究的問題是：1.完成整項工程至少需要多少時間？2.哪些活動是影響工程進度的關鍵？

由於在AOE-網中有些活動可以並行進行，所以完成工程的最短時間是從開始點到完成點的最長路徑的長度(這裡所說的路徑長度是指路徑上各活動持續時間之和，不是路徑上弧的數目)。路徑長度最長的路徑叫做關鍵路徑(Critical path)。

假設開始點是v1，從v1到vi的最長路徑叫做時間vi的最早發生時間。這個時間決定了所有以vi為尾的弧所表示的活動的最早開始時間。我們用e(i)表示活動ai的最早開始時間。還可以定義一個活動開始的最遲時間l(i)，這是在不推遲整個工程完成的前提下，活動ai最遲必須開始進行的時間。兩者之差l(i)-e(i)意味著完成活動ai的時間餘量。當這個時間餘量等於0的時候，也即是l(i)=e(i)的活動，我們稱其為關鍵活動。顯然，關鍵路徑上的所有活動都是關鍵活動，因此提前完成非關鍵活動並不能加快工程的進度。

因此，分析關鍵路徑的目的是辨別哪些是關鍵活動，以便爭取提高關鍵活動的功效，縮短整個工期。

4． 如何實現關鍵路徑？

由上面的分析可知，辨別關鍵活動就是要找e(i)=l(i)的活動。為了求得e(i)和l(i)，首先應求得事件的最早發生時間ve(j)和最遲發生時間vl(j)。如果活動ai由弧j,k表示，其持續時間記為dut(j,k)，則有如下關係

e(i) = ve(j)

l(i) = vl(k) – dut(j,k)

求解ve(j)和vl(j)需分兩個步進行：

1） 從ve(0)=0開始向前推進求得ve(j)

Ve(j) = Max{ve(i) + dut(i,j) };i,j屬於T，j=1,2…,n-1

其中T是所有以第j個頂點為頭的弧的集合。

2） 從vl(n-1) = ve(n-1)起向後推進求得vl(j)

vl(i) = Min{vl(j) – dut(i,j};i,j屬於S，i=n-2,…,0

其中，S是所有以第i個頂點為尾的弧的集合。

這兩個遞推公式的計算必須分別在拓撲有序和逆拓撲有序的前提先進行。也就是說，ve(j-1)必須在vj的所有前驅的最早發生時間求得之後才能確定，而vl(j-1)必須在Vj的所有後繼的最遲發生時間求得之後才能確定。因此可以在拓撲排序的基礎上計算ve(j-1)和vl(j-1)。

具體演算法描述如下：

1． 輸入e條弧j,k，建立AOE-網的存儲結構。

2． 拓撲排序，並求得ve[]。從源點V0出發，令ve[0]=0,按拓撲有序求其餘各頂點的最早發生時間ve[i]。如果得到的拓撲有序序列中頂點個數小於網中頂點數n，則說明網中存在環，不能求關鍵路徑，演算法終止；否則執行步驟3。

3． 拓撲逆序，求得vl[]。從匯點Vn出發，令vl[n-1] = ve[n-1]，按逆拓撲有序求其餘各頂點的最遲發生時間vl[i]。

4． 求得關鍵路徑。根據各頂點的ve和vl值，求每條弧s的最早開始時間e(s)和最遲開始時間l(s)。若某條弧滿足條件e(s) = l(s)，則為關鍵活動。

為了能按逆序拓撲有序序列的順序計算各個頂點的vl值，需記下在拓撲排序的過程中求得的拓撲有序序列，這就需要在拓撲排序演算法中，增設一個棧，以記錄拓撲有序序列，則在計算求得各頂點的ve值之後，從棧頂到棧底便為逆拓撲有序序列。

package graph;

import java.util.*;

public class Grph_CriticalPath 

{

Graph_AdjList adjList;

StackInteger T = new StackInteger(); 

int ve[];

int vl[];

final int max = 10000;

public Grph_CriticalPath(Graph_AdjList adjList)                   //圖的存儲結構是用的鄰接表

{

this.adjList = adjList;

int length = adjList.vetexValue.length;

ve = new int[length];

vl = new int[length];

for(int i=0;ilength;i++)

{

ve[i] = 0;

vl[i] = max;

}

}

public void getCriticalPath()

{

topologicalOrder();

int t = T.pop();

T.push(t);

vl[t] = ve[t];

while(!T.isEmpty())

{

int j = T.pop();

for(Graph_AdjList.ArcNode p = adjList.vetex[j].firstArc; p!=null ;p = p.next)

{

int k = p.adjvex;

if(vl[k]-p.weightvl[j])

{

vl[j] = vl[k]-p.weight;

}

}

}

for(int i=0;ive.length;i++)

{

for(Graph_AdjList.ArcNode p = adjList.vetex[i].firstArc; p!=null ;p = p.next)

{

int k = p.adjvex;

int ee = ve[i];

int el = vl[k]-p.weight;

if(ee==el)

{

System.out.print(i+”,”+k+”     “);

}

}

}

}

public void topologicalOrder()

{

StackInteger S = new StackInteger();

S.push(0);

int count = 0;

while(!S.isEmpty())

{

int j = S.pop();

T.push(j);

count++;

Graph_AdjList.ArcNode p = null;

for(p = adjList.vetex[j].firstArc; p!=null ;p = p.next)

{

int k = p.adjvex;

if(–adjList.degree[k]==0)

{

S.push(k);

}

if(ve[j]+p.weightve[k])

{

ve[k] = ve[j]+p.weight;

}

}

}

if(countadjList.vetexValue.length)

{

System.out.println(“圖中存在環路！”);

return;

}

}

public void print()

{

while(!T.isEmpty())

{

System.out.print(T.pop()+”     “);

}

}

public void printVel()

{

System.out.println();

for(int i=0;ive.length;i++)

{

System.out.print(ve[i]+”    “);

}

System.out.println();

for(int i=0;ivl.length;i++)

{

System.out.print(vl[i]+”    “);

}

}

}

轉自：

一個簡單的演算法演示程序(JAVA語言實現)

還真敢要，別說5分了，5塊錢也沒人幫你做，自己想辦法吧，懶鬼