?? simplessp.java
字號:
public class SimpleSSP {
// simple schema
final int MAX=5000;
public int n;
public int length[][];
private int dist[];
private boolean s[];
public SimpleSSP (AdjGraph G,int nn){
n=nn;
length =new int [n][n];
for (int i=0;i<n;i++)
for (int j=0;j<n;j++){
length[i][j]=G.getWeight(i,j);
//read from the adjacent list graph and store the value into the length matrix
}
dist=new int[n];
s=new boolean[n];
}
public int[] ShortestPath(int v){
for(int i=0;i<=n-1;i++){
s[i]=false;
dist[i]=length[v][i];
}
s[v]=true;
dist[v]=0;
for(int i=0;i<n-2;i++){
int u=choose();
// choose the minimum node
s[u]=true;
// if u has been chosen mark it with true
for(int w=0;w<=n-1;w++){
if(!s[w]){
if(dist[u]+length[u][w]<dist[w]){
// if the current cost is less than history
dist[w]=dist[u]+length[u][w];
// update the dist[]
}
}
}
}
return dist;
}
public int choose(){
// choose the minimum node in the graph
int temp=MAX;
int index=0;
for(int i=0;i<=n-1;i++){
if(s[i]==false&&dist[i]<=temp){
temp=dist[i];
index=i;
}
}
return index;
}
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -