<!--oiuy = setTimeout("Initialize_2()", 5000)SPARSITY = new Array(0,0,5,10,20,30,40,50,60,70,80,90,100,100)Status = "Idle2"REDARROW = new Image()REDARROW.src = "img/red_arrow.gif"BLANKARROW = new Image()BLANKARROW.src = "img/blank_arrow.gif"REDSQUARE = new Image()REDSQUARE.src = "img/red_square.gif"BLUESQUARE = new Image()BLUESQUARE.src = "img/blue_solid.gif"GREENSQUARE = new Image()GREENSQUARE.src = "img/green_solid.gif"GOLDSQUARE = new Image()GOLDSQUARE.src = "img/gold_solid.gif"BLANKSQUARE = new Image()BLANKSQUARE.src = "img/blank_square.gif"REDVARROW = new Image()REDVARROW.src = "img/red_varrow.gif"BLANKVARROW = new Image()BLANKVARROW.src = "img/blank_varrow.gif"END = new Image()END.src = "img/face.gif"ITER2 = 1STATUS_2 = "Idle"n2 = 10function Initialize_2(){form_2 = window.document.forms.dijkstra2Fill_In_2(form_2)}function Clear_2(form){if(STATUS_2 != "Idle"){return}for(i=1;i<=n2;i++){	for(j=1;j<=n2;j++){		eval('form.d_' + i + '_' + j + '.value =" * "')					}			}STATUS_2 ="Idle"form.noticeboard.value = "Distance matrix was cleared."}function Fill_In_2(form){if(STATUS_2  != "Idle"){return}for(i=1;i<=n2;i++){	for(j=1;j<=n2;j++){		eval('form.d_' + i + '_' + j + '.value =" * "')					}			}sparsity = form.sparsity.selectedIndexcycle = form.cycle.selectedIndexCycle = trueif(cycle == 1) {Cycle=false}var s = SPARSITY[sparsity]/100for(i=1;i<=n2;i++){if(!Cycle){jj = i+1} else {jj = 1} for(j=jj;j<=n2;j++){var r = Math.random()if( r < s) {continue}if(i == j){continue}if(j == 1){continue}var dd = Math.floor(1 + Math.random()*n2 + 0.5)eval('form.d_' + i + '_' + j + '.value =' + dd)	}	}STATUS_2 ="Idle"form.noticeboard.value = "A new problem was generated. \nClick the 'Start' button to commence the solution procedure."}function Start_2(form){if(STATUS_2 != "Idle"){return}Clear_2_algor(form)Read_2(form)Initialize_alog2(form)}function Message_2(form,txt){form.noticeboard.value = txt}function Next_2(form){if(STATUS_2 =="Idle"){return}if(STATUS_2 == "F"){Update_F_2(form);return}if(STATUS_2 == "U"){Update_U_2(form);return}if(STATUS_2 == "k"){Update_k_2(form);return}if(STATUS_2 == "G"){Update_G_2(form);return}if(STATUS_2 == "NEXT_K"){Next_k_2(form,KOPT_2);return}}function Clean_2(form){for(j=1;j<=n2;j++){eval('form.d_k_' + j + '.value=""')eval('form.df_k_' + j + '.value=""')eval('form.ff_k_' + j + '.value=""')eval('form.uu_k_' + j + '.value=""')eval('form.nk_k_' + j + '.value=""')	}}function Read_2(form){D = new Array()for(i=1;i<=n2;i++){	D[i] = new Array()	for(j=1;j<=n2;j++){		dd = 1*eval('form.d_' + i + '_' + j + '.value')		if(isNaN(dd)){		D[i][j] = Infinity		eval('form.d_' + i + '_' + j + '.value = "*"')				} 		else {D[i][j] = Number(dd)				}				}			}S= new Array()for(i=1;i<=n2;i++){	S[i] = new Array()	for(k=1;k<=n2;k++){	if(D[i][k] !=Infinity){S[i][S[i].length] = k} 				}			}		}function Initialize_alog2(form){STATUS_2 = "BUSY"F2 = new Array()U2 = new Array()NF2 = new Array()NU2 = new Array()k2 = 1KOPT_2 = 1for(j=1;j<=n2;j++){	eval('form.F_' + j +'.value= " * "')	F2[j] = Infinity 	NF2[j] = Infinity	eval('form.U_' + j +'.value= " + "' )	U2[j] = true	NU2[j] = true			}form.k_1.value = " + "form.F_1.value = 0STATUS_2 = "U"form.iteration.value = ITER2F2[1] = 0NF2[1] = 0window.document.images.arrow_u_2.src=REDARROW.srcwindow.document.images.arrow_f_2.src=BLANKARROW.srcwindow.document.images.city_1.src=GREENSQUARE.srcwindow.document.images.new_U.src=REDSQUARE.srcwindow.document.images.end.src=BLANKSQUARE.srcMessage_2(form,"Initialization completed. Currently k = 0. \nClick the 'Next' button to execute the next step of the algorithm.")}function Update_G_2(form){if(STATUS_2 != "G"){return}for(j=1;j<=n2;j++){	eval('form.d_k_' + j + '.value=" * "')if(D[k2][j] < Infinity ){		eval('form.d_k_' + j + '.value=' + D[k2][j])						}			}for(j=0;j<S[k2].length;j++){	var x = S[k2][j]	NF2[x] = D[k2][x] + F2[k2]		}for(j=1;j<=n2;j++){	if(!U2[j]){continue}	var y = NF2[j]	if(NF2[j] == Infinity){y = " * "}	eval('form.df_k_' + j + '.value= "' + y + '"')			}window.document.images.arrow_g_2.src=BLANKARROW.srcwindow.document.images.arrow_f_2.src=REDARROW.srcwindow.document.images.new_F.src=REDSQUARE.srcMessage_2(form,"The values of G(k,j) for j in U^S(k) were computed. \nClick the 'Next' button to execute the next step of the algorithm.")STATUS_2 = "F"}function Update_F_2(form){if(STATUS_2 != "F"){return}for(j=1;j<=n2;j++){	if(U2[j]){	F2[j] = Math.min(F2[j],NF2[j])}	var y = F2[j]	if(F2[j] == Infinity){y = " * "}	eval('form.ff_k_' + j + '.value= "' + y + '"')	NF2[j] = F2[j]			}window.document.images.arrow_f_2.src=BLANKARROW.srcwindow.document.images.arrow_k_2.src=REDARROW.srcwindow.document.images.new_F.src=BLANKSQUARE.srcwindow.document.images.new_k.src=REDSQUARE.srcSTATUS_2 = "k"Message_2(form,"Update of F for city k = " + k2 + " has been completed. The new values of {F[j]} are listed in the new F row.  The relevant values of j are those corresponding to the numeric entries in the D(k,j) row. These are the cities that have direct links to city k =" + k2 + '.\nClick the "Next" button to execute the next step of the algorithm.'  )}function Update_U_2(form){if(STATUS_2 != "U"){return}U2[k2] = falsefor(j=1;j<=n2;j++){	y = " + " 	if(U2[j] == false) { y = ""}	eval('form.uu_k_' + j + '.value= "' + y + '"')			}window.document.images.arrow_u_2.src=BLANKARROW.srcwindow.document.images.arrow_g_2.src=REDARROW.srcwindow.document.images.new_U.src=BLANKSQUARE.srcSTATUS_2 = "G"Message_2(form,"Update of U for city k = " + k2 + " has been completed. City " + k2 + " were deleted from the old set U.\nClick the 'Next' button to execute the next step of the algorithm."  )}function Update_k_2(form){if(STATUS_2 != "k"){return}var optf = Infinitykopt = 0SUMU = 0KOPT_2 = 0for(j=1;j<=n2;j++){	if(!U2[j]){continue}	SUMU += 1	if(F2[j] <optf){optf = F2[j] ; kopt = j} 			}if(kopt == 0){STATUS_2 = "End"; End_2(form); return}kk2 = koptKOPT_2 = kopteval('form.nk_k_' + kk2 + '.value=" + "')window.document.images.new_k.src=BLANKSQUARE.srcwindow.document.images.arrow_k_2.src=BLANKARROW.srceval('window.document.images.new_k_' + kk2 + '.src=REDVARROW.src')eval('window.document.images.city_' + k2 + '.src=BLUESQUARE.src')STATUS_2 = "NEXT_K"if(SUMU == 1){STATUS_2 = "End"; End_2(form); return}Message_2(form,"Update of k = " + k2 + " has been completed. The next city to be processed is city " + KOPT_2 + ".  This city was selected because F[" + KOPT_2 +  "] = " + F2[KOPT_2] + " is the smallest value of F[j] for all j in (the new) set U.\nClick the 'Next' button to execute the next step of the algorithm." )}function Next_k_2(form,kkk){if(STATUS_2 !="NEXT_K"){return}ITER2 += 1form.iteration.value = ITER2if(kkk != kopt){return}eval('window.document.images.new_k_' + kkk + '.src=BLANKVARROW.src')eval('window.document.images.city_' + k2 + '.src=BLUESQUARE.src')var SUMU = 0for(j=1;j<=n2;j++){	if(!U2[j]){continue}	SUMU += 1			}if(SUMU == 1){STATUS_2 = "End";return}k2 = koptKOPT_2 =kopteval('window.document.images.city_' + k2 + '.src=GREENSQUARE.src')STATUS_2 = "U"window.document.images.arrow_u_2.src=REDARROW.srcwindow.document.images.new_U.src=REDSQUARE.srcfor(j=1;j<=n2;j++){	eval('form.F_' + j + '.value = form.ff_k_' + j + '.value');	eval('form.U_' + j + '.value = form.uu_k_' + j + '.value');	eval('form.k_' + j + '.value = form.nk_k_' + j + '.value');	eval('form.ff_k_' + j + '.value = ""')	eval('form.uu_k_' + j + '.value = ""')	eval('form.nk_k_' + j + '.value = ""')	eval('form.df_k_' + j + '.value = ""')	eval('form.d_k_' + j + '.value = ""')			}Message_2(form,"The city currently being processed is k = " + KOPT_2 +  ".\nClick the 'Next' button to execute the next step of the algorithm.")}function End_2(form){if(kopt > 0){	eval('window.document.images.new_k_' + kopt + '.src=BLANKVARROW.src')		}for(j=1;j<=n2;j++){eval('window.document.images.city_' + j + '.src=BLANKSQUARE.src')	}window.document.images.arrow_f_2.src=BLANKARROW.srcwindow.document.images.arrow_k_2.src=BLANKARROW.srcwindow.document.images.arrow_u_2.src=BLANKARROW.srcwindow.document.images.new_F.src=BLANKSQUARE.srcwindow.document.images.new_U.src=BLANKSQUARE.srcwindow.document.images.new_k.src=BLANKSQUARE.srcform.iteration.value = ""var tif((SUMU > 1) && (KOPT_2 == 0)){t = "Algorithm terminated (F(k) = infinity): " + SUMU  + " cities are not reachable from city 1."}if((SUMU == 1) && (KOPT_2 == 0)){t = "Algorithm terminated (|U| = 1 and F[k] = infimnity): one  city is not reachable from city 1."}if((SUMU == 1) && (KOPT_2 != 0)){t = "Algorithm terminated (|U| = 1):  all cities are reachable from city 1."}Message_2(form,t + '\n+++++++++++++\nYou may now wish to generate and solve a new problem. If so, select the parameters using the "sparsity" and "cyclic" menues and then click the "Fill-In" button to generate a new distance matrix based on these parameters. This done, click the "Start" button to solve the new problem.')window.document.images.end.src=END.srcSTATUS_2 ="Idle"}function Clear_2_algor(form){for(j=1;j<=n2;j++){eval('window.document.images.new_k_' + j + '.src=BLANKVARROW.src')eval('window.document.images.city_' + j + '.src=BLANKSQUARE.src')eval('form.F_' + j + '.value = " "')eval('form.U_' + j + '.value = " "')eval('form.k_' + j + '.value = " "')eval('form.d_k_' + j + '.value = " "')eval('form.df_k_' + j + '.value = " "')eval('form.ff_k_' + j + '.value = " "')eval('form.uu_k_' + j + '.value = " "')eval('form.nk_k_' + j + '.value = " "')eval('window.document.images.new_k' + '_' + j + '.src=BLANKVARROW.src')		}window.document.images.arrow_f_2.src=BLANKARROW.srcwindow.document.images.arrow_k_2.src=BLANKARROW.srcwindow.document.images.arrow_u_2.src=BLANKARROW.srcwindow.document.images.new_F.src=BLANKSQUARE.srcwindow.document.images.new_U.src=BLANKSQUARE.srcwindow.document.images.new_k.src=BLANKSQUARE.srcform.noticeboard.value="Idle."form.iteration.value = ""STATUS_2 ="Idle"}function Help_2(form){WIN_Help2 = open('WIN_Help2.html','WIN_Help2',"width=500,height=300,title='Help'")oioi = setTimeout("WIN_Help2.focus()",1000) }function Initialize(){uytr = window.frames[0].location="module_2_up.html"n = 20formup = top.up.document.forms[0]Create(n)//Fill_In(n)alert("initialize - algo_2")}function Help(){WIN2_Help = open('WIN2_Help.html','WIN2_Help',"width=500,height=350,title='Help'")oioi = setTimeout("WIN2_Help.focus()",1000)alert("help algo_2") }function Change(){if(Status != "Idle"){top.up.document.forms[0].N.selectedIndex=0; return}N = 10 + 5*(top.up.document.forms[0].N.selectedIndex -1)formup = top.up.document.forms[0]formup.N.selectedIndex = 0Create(N)}function Create(N){var n = NFont = '<font face="verdana,arial">'var t = '<html><body bgcolor="white" text="black">'t += '<table height=100% align="center"><tr><td><table align="center" cellpadding=0 cellspacing=0 border=1 bordercolor="darkred">'t += '<form><tr><td align="center">'t += '<table align="center" border=0 cellspacing=0 cellpadding=0 bordercolor="white">' for(i=1;i<=n;i++){t += '<tr align="center">'for(j=1;j<=n;j++){ t += '<td><a href="javascript:void(0)" onmouseover="top.Over(' + i + ',' + j + ')" onmouseout="top.Out(' + i + ',' + j + ')" onClick="top.Click(' + i + ',' +j +')"><img src="img/lightgrey.gif" name="d_' + i + '_' + j +  '"  border=0 width=10 ></a></td>'} 	}t +='<tr></table></td><tr></form></table></td></tr></table>'t += '</body></html>'window.down.document.clear()window.down.document.open()window.down.document.write(t)window.down.document.close()}function Fill_In(n){ returnvar dr = ur - lrvar s = SPARSITY[sparsity]/100for(i=1;i<=n;i++){if(!Cycle){jj = i+1} else {jj = 1} for(j=jj;j<=n;j++){var r = Math.random()if( r < s) {continue}var sss = 1if(Math.random() < sign ) {sss = -1} var dd = Math.floor(lr + Math.random()*dr + 0.5)eval('frames[1].document.forms[0].d_' + i + '_' + j + '.value =' + (dd*sss))	}	}top.down.document.forms[0].status.value="Generated new problem. Now, idle ..."Status = "Idle"}function Solve(){if(Status != "Idle"){return} Status = "Solve"window.down.document.forms[0].status.value="Preprocessing  ...."Read()Initialize_f()Suc_app()}function Read(){D = new Array()for(i=1;i<=n;i++){	D[i] = new Array()	for(j=1;j<=n;j++){		dd = eval('top.down.document.forms[0].d_' + i + '_' + j + '.value')		if(isNaN(dd)){D[i][j] = Infinity} else {D[i][j] = Number(dd)}				}			}P= new Array()for(j=1;j<=n;j++){	P[j] = new Array()	for(k=1;k<=n;k++){	if(D[k][j] !=Infinity){P[j][P[j].length] = k} 				}			}		}function Initialize_f(){F = new Array()KNN = new Array()Flag = new Array()for(j=1;j<=n;j++){	F[j] = Infinity	KNN[j] = 0	Flag[j] = false	eval('top.down.document.forms[0].f_' + j + '.value = " * "')	}F[1] = 0FN = F[n]KN = 0ITER = 0top.down.document.forms[0].f_1.value = 0}function Suc_app(){ITER += 1top.down.document.forms[0].status.value = "Iteration No. " + ITER + " of the SA procedure ..."FLAG = falsefor(j=1;j<=n;j++){	for(x=0;x<P[j].length;x++){	var dd = P[j][x]	var dd = F[dd] + D[dd][j]	if(dd  < F[j] ){F[j] = dd ; Flag[j]  = true ; FLAG = true} 							}			}if(!FLAG){End(); return}for(j=1;j<=n;j++){if(Flag[j] ){KNN[j] += 1}	}if(F[n] < FN){FN = F[n] ; KN = 0} else {KN += 1}  if(KN > (n+1)){End(); return}if(KNN[n]  > (n+1)){Unbounded(); return}  tre = setTimeout('Suc_app()',0)Update_F()}function Update_F(){for(j=1;j<=n;j++){var dd = Math.min(Infinity,F[j])if(KNN[j] >= (n+1)){dd = "UB"; F[j] = -Infinity} if(dd == Infinity){dd = " *"} eval('top.down.document.forms[0].f_' + j + '.value = "' + dd + '"')	}}function Unbounded(){for(j=1;j<=n;j++){var dd = Math.min(Infinity,F[j])if(KNN[j] >= (n+1)){dd = "UB"; F[j] = -Infinity} if(dd == Infinity){dd = " *"} eval('top.down.document.forms[0].f_' + j + '.value = "' + dd + '"')	}End()}function End(){Status = "Idle"top.down.document.forms[0].status.value ="Problem solved in " + ITER + " SA iterations. Now idle ..."}function Over(i,j){top.up.document.forms[0].x.value=itop.up.document.forms[0].y.value=j}function Out(i,j){top.up.document.forms[0].x.value=""top.up.document.forms[0].y.value=""}function Click(i,j){var a = 1if(Status == "Home"){SRC = RED.src}if(Status == "Destination"){ SRC = BLUE.src} if(Status == "Idle"){SRC = eval('top.down.document.images.d_' + i + '_' + j + '.src')var ii = SRC.indexOf("grey.gif")if(ii == -1 ){SRC = GREY.src; a = -1} else {SRC=BLACK.src; X=i;Y=j}   } eval('top.down.document.images.d_' + i + '_' + j + '.src= SRC')K += atop.up.document.forms[0].n.value = KStatus = "Idle"}function Home(){Status = "Home"}function Destination(){Status="Destination"}// -->