算法题！！！求解

Question

输入一张图： 
说明：边的数值代表从A到B的代价；输出：从a到G的路线，要求，代价最小：求解：算法：
1
先随便输出5条路径：
比如：abeg adbeg  adfg  abceg  adefg
2，计算每条路径的健康度：也就是花费：
比如：abeg＝7+7+9；
3，选出5条中最健康的4条。两两进行交配。交配就是如果有相同节点，则交换路径：
比如：
abc  d  efg
afscv d   fdsg他们俩交换以后是
afscv  d  efg
abc d   fdsg然后在计算这四条的健康度。以此类推。直到只有一条

Answer 1

目测有现成的类提供解法，先到util里面找？

Answer 2

思想本身就不是最权威的，而且，这种问题最好自己去实现，不要总是想着用别人提供好的API，虽然咱身为码工，但是一定要有成为设计人员的目标。
试试用迪杰斯特拉算法，参考http://baike.baidu.com/view/1939816.htm。
基本思想：
将图G中所有的顶点V分成两个顶点集合S和T。以v为源点已经确定了最短路径的终点并入S集合中，S初始时只含顶点v,T则是尚未确定到源点v最短路径的顶点集合。然后每次从T集合中选择S集合点中到T路径最短的那个点，并加入到集合S中，并把这个点从集合T删除。直到T集合为空为止。 
首先，你要明白“图”是点的集合与关系的集合这两个集合组合在一起的数据结构，而“邻接表”是最常用的描述无向图或者有向图的方法
图论算法我研究过一段时间，所以这里就把我写的代码直接贴上去了，会有一些用不到的代码，请大家见谅：
迪杰斯特拉算法的类，对照这个类来看下面三个类吧！
package tm.cao.tu;import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
//专门用于迪杰斯特拉算法的类 public class Dijkstra{
//顶点集合
private List<DingDian> dianList;
//关系集合
private List<GuanXi> guanxiList;
public List<DingDian> getDianList() {
return dianList;
}
public List<GuanXi> getGuanxiList() {
return guanxiList;
}
public void setDianList(List<DingDian> dianList) {
this.dianList = dianList;
}
public void setGuanxiList(List<GuanXi> guanxiList) {
this.guanxiList = guanxiList;
}
//构造器
public Dijkstra(List<DingDian> dianList, List<GuanXi> guanxiList, Integer flag) {
super();
this.dianList = dianList;
//有向图
if(flag==0){
this.guanxiList=guanxiList;
}else if(flag==1){
//如果是无向图，则需要加入反序的关系
List<GuanXi> list2=new ArrayList<GuanXi>();
for(GuanXi gx:guanxiList){
GuanXi fan=new GuanXi(gx.getWei(), gx.getTou(), gx.getQuan());
list2.add(fan);
}
guanxiList.addAll(list2);
this.guanxiList=guanxiList;
}else{
//无论如何也不扩展边集  相当于只创建边集数组
this.guanxiList=guanxiList;
}
}
//构造邻接表
public void createLingJieBiao(){
if(guanxiList.size()>0){
Collections.sort(guanxiList);
}
for(GuanXi gx:guanxiList){
DingDian tou=gx.getTou();
Hu q=new Hu(gx.getWei(), gx.getQuan());
q.setId(gx.getId());
//入度+1 对应于拓扑排序
DingDian wei=gx.getWei();
int rudu=wei.getRudu();
rudu++;
wei.setRudu(rudu);
if(tou.getFirstHu()==null){
tou.setFirstHu(q);
}else{
Hu p=tou.getFirstHu();
while(p.getNextHu()!=null){
p=p.getNextHu();
}
p.setNextHu(q);
}
}
}
/**迪杰斯克拉算法  http://baike.baidu.com/view/1939816.htm
 *sList:需要求的顶点集合 一开始只有一个点 dist属性：记录长度，path属性：记录路径的数组
 */
public List<DingDian> disjaktra(DingDian which){
this.createLingJieBiao();
List<DingDian> sList=new ArrayList<DingDian>();
//为了计算dist方便 设置一个动态集合 用于记录dist已经不是null的点
List<DingDian> dongtaiList=new ArrayList<DingDian>();
//所需要求的点已经被遍历过
which.setShenduFlag(1);
//先设置第一个点的相关属性
sList.add(which);
which.setDist(0);
//如果他没有出度  则没有通路
if(which.getFirstHu()==null){
System.out.println("没有通路！");
return null;
}else{
//遍历邻接表的所有弧  设置相应点的dist以及path  但并不添加到sList
this.findAllChudu(which, dongtaiList);
}
while(dongtaiList.size()>0){
DingDian minDian=dongtaiList.get(0);
Integer min=minDian.getDist();
//擂台算法找出最小的dist
for(DingDian d:dongtaiList){
if(d.getDist()<min){
min=d.getDist();
minDian=d;
}
}
minDian.setShenduFlag(1);
dongtaiList.remove(minDian);
sList.add(minDian);
if(minDian.getFirstHu()==null){
continue;
}else{
//遍历这个点的邻接表
this.findAllChudu(minDian, dongtaiList);
//继续
}
}
return sList;

}
//遍历这个顶点的邻接表 找到所有的弧
public void findAllChudu(DingDian minDian,List<DingDian> dongtaiList){
Hu hu=minDian.getFirstHu();
while(hu!=null){
DingDian find=hu.getDian();
//对于对称关系的无向图 如果该点已经被遍历过 则跳过
if(find.getShenduFlag()==1){
hu=hu.getNextHu();
continue;
}
// 算出值最小的dist或者上一个（dist+quan）
if(find.getDist()==null){
//如果没有 则把他的前驱结点的路径添加到自己的路径
find.setDist(hu.getQuan()+minDian.getDist());
find.getPath().addAll(minDian.getPath());
find.getPath().add(minDian);
}
else{
if(find.getDist()<(hu.getQuan()+minDian.getDist())){
}else{
//如果这次加起来的路径比上次的小 则先removeAl 然后add  minDian 的路径以及minDian
find.setDist(hu.getQuan()+minDian.getDist());
find.getPath().clear();
find.getPath().addAll(minDian.getPath());
find.getPath().add(minDian);
}
}
if(!dongtaiList.contains(find)){
dongtaiList.add(find);
}
hu=hu.getNextHu();
}
}
}顶点类：
package tm.cao.tu;import java.util.ArrayList;
import java.util.List;//所有的顶点
public class DingDian implements Comparable<DingDian>{
//迪杰斯特拉的dist长度
private Integer dist;
//记录路径的集合
private List<DingDian> path=new ArrayList<DingDian>();
public Integer getDist() {
return dist;
} public void setDist(Integer dist) {
this.dist = dist;
}
public List<DingDian> getPath() {
return path;
}
public void setPath(List<DingDian> path) {
this.path = path;
}
//数据域
private String data;
//第一个弧  对应十字链表的firstOut
private Hu firstHu;
public String getData() {
return data;
}
public Hu getFirstHu() {
return firstHu;
}
public void setData(String data) {
this.data = data;
}
public void setFirstHu(Hu firstHu) {
this.firstHu = firstHu;
}
public DingDian(String data, Hu firstHu) {
super();
this.data = data;
this.firstHu = firstHu;
}
public DingDian() {
super();
}
public DingDian(String data) {
super();
this.data = data;
}
@Override
public String toString() {
return "DingDian [data=" + data + "]";
}
//第一个进来的弧
private Hu firstIn;
public Hu getFirstIn() {
return firstIn;
}
public void setFirstIn(Hu firstIn) {
this.firstIn = firstIn;
}
public int compareTo(DingDian other) {
return data.compareTo(other.getData());
}
//遍历时候的Flag  0表示未遍历 1表示已经遍历
private int shenduFlag;
public int getShenduFlag() {
return shenduFlag;
}
public void setShenduFlag(int shenduFlag) {
this.shenduFlag = shenduFlag;
}
//非递归深度遍历的时候当前弧
private Hu currentHu;
public Hu getCurrentHu() {
return currentHu;
}
public void setCurrentHu(Hu currentHu) {
this.currentHu = currentHu;
}
//prim算法的Flag
private int primFlag=1;
public int getPrimFlag() {
return primFlag;
}
public void setPrimFlag(int primFlag) {
this.primFlag = primFlag;
}
//为了prim算法方便 所以设置一个整数的id
private int id;
public int getId() {
return id;
}
public void setId(int id) {
this.id = id;
}
public DingDian(String data, int id) {
super();
this.data = data;
this.id = id;
}
//记录入度 用于拓扑排序
private int rudu;
public int getRudu() {
return rudu;
}
public void setRudu(int rudu) {
this.rudu = rudu;
}
//最早发生时间
private int ee;
//最晚发生时间
private int le;
public int getEe() {
return ee;
}
public int getLe() {
return le;
}
public void setEe(int ee) {
this.ee = ee;
}
public void setLe(int le) {
this.le = le;
}}关系类：
package tm.cao.tu;
//关系
public class GuanXi implements Comparable<GuanXi>{public GuanXi() {
super();
}
//权
private Integer quan;
public Integer getQuan() {
return quan;
}
public void setQuan(Integer quan) {
this.quan = quan;
}//直接设置头和尾
private DingDian tou;
private DingDian wei;
public DingDian getTou() {
return tou;
}
public DingDian getWei() {
return wei;
}
public void setTou(DingDian tou) {
this.tou = tou;
}
public void setWei(DingDian wei) {
this.wei = wei;
}public GuanXi(DingDian tou, DingDian wei,Integer quan) {
super();
this.quan = quan;
this.tou = tou;
this.wei = wei;
}
@Override
public String toString() {
return "GuanXi [data1=" + tou.getData() + ", data2=" + wei.getData() + ", quan=" + quan
+ "]";
}
private int sortFlag;public int getSortFlag() {
return sortFlag;
}
public void setSortFlag(int sortFlag) {
this.sortFlag = sortFlag;
}
//先比较权的大小 然后头的大小 然后比较尾的大小  排序权值 适用于Kruscal算法
public int compareTo(GuanXi other) {
//如果需要排序权
if(this.getSortFlag()==1){
return this.getQuan().compareTo(other.getQuan());
}
else if(!this.getTou().getData().equals(other.getTou().getData())){
return this.getTou().getData().compareTo(other.getTou().getData());
}else{
return this.getWei().getData().compareTo(other.getWei().getData());
}
}
public GuanXi(DingDian tou, DingDian wei, Integer quan, int sortFlag) {
super();
this.quan = quan;
this.tou = tou;
this.wei = wei;
this.sortFlag = sortFlag;
}
public GuanXi(DingDian tou, DingDian wei) {
super();
this.tou = tou;
this.wei = wei;
}
//为了计算方便
private String id;
public String getId() {
return id;
}
public void setId(String id) {
this.id = id;
}
public GuanXi(Integer quan, DingDian tou, DingDian wei, String id) {
super();
this.quan = quan;
this.tou = tou;
this.wei = wei;
this.id = id;
}}弧类：
package tm.cao.tu;
//所有的弧
public class Hu {
//为了表示方便 所以有id
private String id;

public String getId() {
return id;
}
public void setId(String id) {
this.id = id;
}
//所指向的点 对应邻接表  此点为弧所指向的点
private DingDian dian;
//权
private Integer quan;
//下一个弧
private Hu nextHu;public Integer getQuan() {
return quan;
}
public Hu getNextHu() {
return nextHu;
}public void setQuan(Integer quan) {
this.quan = quan;
}
public void setNextHu(Hu nextHu) {
this.nextHu = nextHu;
}
public DingDian getDian() {
return dian;
}
public void setDian(DingDian dian) {
this.dian = dian;
}
public Hu() {
super();
}public Hu(Integer quan, Hu nextHu, DingDian dian) {
super();
this.quan = quan;
this.nextHu = nextHu;
this.dian = dian;
}public Hu(DingDian dian, Integer quan) {
super();
this.dian = dian;
this.quan = quan;
}
//以下四个属性 对应十字链表
private String qidian;
private String zhongdian;
private Hu hlink;
private Hu tlink;public String getQidian() {
return qidian;
}
public String getZhongdian() {
return zhongdian;
}
public Hu getHlink() {
return hlink;
}
public Hu getTlink() {
return tlink;
}
public void setQidian(String qidian) {
this.qidian = qidian;
}
public void setZhongdian(String zhongdian) {
this.zhongdian = zhongdian;
}
public void setHlink(Hu hlink) {
this.hlink = hlink;
}
public void setTlink(Hu tlink) {
this.tlink = tlink;
}
public Hu(Integer quan, String qidian, String zhongdian, Hu hlink, Hu tlink) {
super();
this.quan = quan;
this.qidian = qidian;
this.zhongdian = zhongdian;
this.hlink = hlink;
this.tlink = tlink;
}
@Override
public String toString() {
return "Hu [id=" + id + ", dian=" + dian + ", quan=" + quan + "]";
}
//关键路径的权
private Integer guanJianQuan;public Integer getGuanJianQuan() {
return guanJianQuan;
}
public void setGuanJianQuan(Integer guanJianQuan) {
this.guanJianQuan = guanJianQuan;
}}

Answer 3

用最短路径算法，即可达到楼主的要求了。
http://java.chinaitlab.com/base/832683.html