關(guān)鍵路徑算法的核心依舊是拓?fù)渑判蛩惴ㄉ婪瓿申P(guān)鍵路徑婆跑，有以下要完成的東西
- 最早發(fā)生時(shí)間的數(shù)組
- 最遲發(fā)生時(shí)間的數(shù)組
- 若某個(gè)點(diǎn)最早和最遲時(shí)間是一致的废离，則說(shuō)明了：這是一個(gè)關(guān)鍵點(diǎn)缴淋，一定在關(guān)鍵路徑上面旱函。
- 點(diǎn)1的最早發(fā)生時(shí)間 = 點(diǎn)2的最遲發(fā)生時(shí)間 - 兩點(diǎn)之前權(quán)值响巢，說(shuō)明了兩個(gè)點(diǎn)連線就在關(guān)鍵路徑上面。
關(guān)于最早發(fā)生時(shí)間的計(jì)算
- 預(yù)制一個(gè)數(shù)組棒妨，讓每一個(gè)點(diǎn)最早時(shí)間都是0
- 從關(guān)鍵路徑（用拓?fù)渑判蛩惴ㄋ愠鰜?lái)）第一個(gè)點(diǎn)開(kāi)始踪古，找到這個(gè)點(diǎn)的所有連接的其他點(diǎn)，找到最小的一個(gè)連接券腔，更新這個(gè)連接對(duì)應(yīng)的端點(diǎn)的最早發(fā)生時(shí)間伏穆；
- 更新完畢每一個(gè)點(diǎn)
關(guān)于最遲發(fā)生時(shí)間的計(jì)算
- 預(yù)制一個(gè)數(shù)組，讓每一個(gè)點(diǎn)最早時(shí)間都是最早發(fā)生時(shí)間中的最大值（也就是數(shù)組中的最后一個(gè)）
- 從關(guān)鍵路徑（用拓?fù)渑判蛩惴ㄋ愠鰜?lái)）最后一個(gè)點(diǎn)開(kāi)始纷纫，找到這個(gè)點(diǎn)的所有連接的其他點(diǎn)枕扫，找到最小的一個(gè)連接，更新這個(gè)連接對(duì)應(yīng)的端點(diǎn)的最遲發(fā)生時(shí)間辱魁；
- 更新完畢每一個(gè)點(diǎn)
//拓?fù)渑判?//頂點(diǎn)
function Vertex(name) {
this.name =name;
this.in = 0;
}
Vertex.prototype.setFirstedge = function(edgeNode) {
this.firstEdge = edgeNode;
edgeNode.adjVex.in++;
};
Vertex.prototype.setNext = function(edgeNode){
var temp = this.firstEdge;
if(!temp){
this.firstEdge = edgeNode;
edgeNode.adjVex.in++;
return;
}else{
while(temp){
var temp1 = temp.next;
if(!temp1){
temp.next = edgeNode;
edgeNode.adjVex.in++;
break;
}else{
temp = temp.next;
}
}
}
}
//邊
function EdgeNode(){
this.adjVex = arguments[0];
this.weight = arguments[1] ? arguments[1] : undefined;
}
//圖
function Graph(vertexs,numEdges){
this.vertexs = vertexs;
this.numVertexs = this.vertexs.length;
this.numEdges =numEdges;
}
//需要引入棧進(jìn)行計(jì)算
function Node(data) {
this.data = data;
}
function Stack(maxSize){
this.maxSize = maxSize;
this.top = -1;
this.data = new Array(maxSize);
}
Stack.prototype.push = function(node){
if(this.top == this.maxSize-1){
return 1;
}
this.top++;
this.data[this.top] = node;
return 0;
}
Stack.prototype.pop = function(){
if(this.top==-1){
return 1;
}
var r = this.data[this.top];
this.data[this.top] = undefined;
this.top--;
return r;
}
Stack.prototype.ergodic = function(){
var s = '';
for (var i = 0; i < this.data.length; i++) {
if(this.data[i]!=null){
s += this.data[i]+',';
}
}
if(s.length){
s = s.substring(0,s.length-1);
}
return s;
}
Stack.prototype.length = function(){
return this.top+1;
}
//拓?fù)湫蛄?Graph.prototype.topologicalSort = function() {
var top = 0,count = 0;
var gettop,k;
var result ='';//結(jié)果
var stack = new Stack(this.numVertexs);
var stack2 = new Stack(this.numVertexs);
var etv = [];
for (var i = 0; i < this.numVertexs; i++) {
etv.push(0);
if(this.vertexs[i].in==0){
stack.push(i);
}
}
while(stack.length()){
gettop = stack.pop();
result += this.vertexs[gettop].name +' ';
count++;
stack2.push(gettop);
for (var e = this.vertexs[gettop].firstEdge; e; e=e.next) {
k = this.vertexs.indexOf(e.adjVex);
if(!(--this.vertexs[k].in)){
stack.push(k);
}
if(etv[gettop]+e.weight>etv[k]){
etv[k] = etv[gettop]+e.weight;
}
}
}
if(count<this.numVertexs){
console.info('發(fā)生錯(cuò)誤烟瞧，有環(huán)路存在');
return false;
}
return {
etv:etv,
stack:stack2
};
};
Graph.prototype.criticalPath = function(){
var topological = this.topologicalSort();
var etv = topological.etv;//最早發(fā)生時(shí)間
var stack = topological.stack;
console.info('可計(jì)算的最早發(fā)生時(shí)間數(shù)組etv:'+etv);
console.info('拓?fù)湫蛄?'+stack.ergodic());
var gettop,k;
var ltv = new Array(this.numVertexs);//最遲發(fā)生時(shí)間
for (var i = 0; i < this.numVertexs; i++) {
ltv[i] = etv[this.numVertexs-1];
}
while(stack.length()){
gettop = stack.pop();
for (var e = this.vertexs[gettop].firstEdge; e; e=e.next) {
k = this.vertexs.indexOf(e.adjVex);
if(ltv[k]-e.weight<ltv[gettop]){
ltv[gettop] = ltv[k] - e.weight;
}
}
}
for (var j = 0; j < this.numVertexs; j++) {
for (var e = this.vertexs[j].firstEdge; e; e=e.next) {
k = this.vertexs.indexOf(e.adjVex);
if(etv[j]==ltv[k]-e.weight){
console.info(this.vertexs[j].name+'到'+this.vertexs[k].name+'('+e.weight+')');
}
}
}
}
var v0 = new Vertex('v0');
var v1 = new Vertex('v1');
var v2 = new Vertex('v2');
var v3 = new Vertex('v3');
var v4 = new Vertex('v4');
var v5 = new Vertex('v5');
var v6 = new Vertex('v6');
var v7 = new Vertex('v7');
var v8 = new Vertex('v8');
var v9 = new Vertex('v9');
v0.setNext(new EdgeNode(v2,4));
v0.setNext(new EdgeNode(v1,3));
v1.setNext(new EdgeNode(v4,6));
v1.setNext(new EdgeNode(v3,5));
v2.setNext(new EdgeNode(v5,7));
v2.setNext(new EdgeNode(v3,8));
v3.setNext(new EdgeNode(v4,3));
v4.setNext(new EdgeNode(v7,4));
v4.setNext(new EdgeNode(v6,9));
v5.setNext(new EdgeNode(v7,6));
v6.setNext(new EdgeNode(v9,2));
v7.setNext(new EdgeNode(v8,5));
v8.setNext(new EdgeNode(v9,3));
var g = new Graph([v0,v1,v2,v3,v4,v5,v6,v7,v8,v9],13);
//g.topologicalSort();
g.criticalPath();
輸出
可計(jì)算的最早發(fā)生時(shí)間數(shù)組etv:0,3,4,12,15,11,24,19,24,27
拓?fù)湫蛄?0,1,2,3,4,6,5,7,8,9
v0到v2(4)
v2到v3(8)
v3到v4(3)
v4到v7(4)
v7到v8(5)
v8到v9(3)
[Finished in 0.1s]
