nearest.txt.txt

用java求最短路径问题的 源程序

csdn ....... :( 

class CShortPath 
{ 
private: 
class Edge 
{ 
private: 
int dest; //the operation of the other vertex of edge 
int weight;//quan zhi 
Edge *link; 

}; 
class Vertex 
{ 
private: 
int adj;//顶点编号 
Edge *link; 
int Visited; //biao ji 
}; 

public: 
void InitE(Vertex head[],int j,int k,int weight); 
void short_path(int v,int w); 
void creat_adj_list(); 
CShortPath(); 
virtual ~CShortPath(); 
}; 
void CShortPath::creat_adj_list() 
{ 
Vertex head[15]; 
for(int i=0;i<15;i++) 
{ 
head[i].link=NULL; 
head[i].adj=i;//mingzi 
head[i].name="站点"; 
} 
InitE(head,0,1,140); 
InitE(head,1,2,675); 
InitE(head,2,3,409); 
InitE(head,3,4,534); 
InitE(head,4,5,511); 
InitE(head,5,6,842); 
InitE(head,6,7,1100); 
InitE(head,7,8,639); 
InitE(head,8,9,607); 
InitE(head,9,10,255); 
InitE(head,2,11,367); 
InitE(head,11,12,622); 
InitE(head,11,13,825); 
InitE(head,13,14,651); 
InitE(head,4,14,349); 
InitE(head,2,8,902); 
InitE(head,2,9,672); 
InitE(head,6,8,967); 
} 
void CShortPath::InitE(Vertex head[],int j,int k,int weight) 
{ 
Edge *p; 
p=new Edge[sizeof(Edge)]; 
p->dest=k; 
p->link=head[j].link; 
p->weight=weight; 
head[j].link=p; 
p=new Edge[sizeof(Edge)]; 
p->dest=j; 
p->link=head[k].link; 
p->weight=weight; 
head[k].link=p; 
} 
void CShortPath::short_path(int v,int w) 
{ 
creat_adj_list(); 
int adj; 
int Distance[25]; 
Edge *q; 
int edges; 
edges=1; 
q=new Edge[sizeof(Edge)]; 
for(int j=0;j<25;j++) 
{ 
Distance[j]=Max; 
head[j].Visited=0; 
} 
q=head[v].link; 
while(q!=NULL) 
{ 
Distance[q->dest]=q->weight; 
q=q->link; 
} 
q=head[v].link; 
head[v].Visited=1; 
while(edges<24) 
{ 
edges++; 
Min=Max; 
for(int i=0;i<25;i++) 
{ 
if(head[i].Visited==0&&Min>Distance[i]) 
{ 
Min=Distance[i]; 
adj=i; 
} 
} 
head[adj].Visited=1; 
q=head[adj].link; 
while(q!=NULL) 
{ 
if(head[q->dest].Visited==0&& 
Distance[adj]+q->weight<Distance[q->dest]) 
{ 
Distance[q->dest]=Distance[adj]+q->weight; 
} 
q=q->link; 
} 
} 
}