无向图最短路径问题升级版
2017-10-04 本文已影响72人
9c0ddf06559c
问题: 无向图G有N个结点，它的边上带有正的权重值。
你从结点1开始走，并且一开始的时候你身上带有M元钱。如果你经过结点i， 那么你就要花掉S[i]元(可以把这想象为收过路费)。如果你没有足够的钱， 就不能从那个结点经过。在这样的限制条件下，找到从结点1到结点N的最短路径。 或者输出该路径不存在。如果存在多条最短路径，那么输出花钱数量最少的那条。 限制：1<N<=100 ; 0<=M<=100 ; 对于每个i，0<=S[i]<=100；
-
分析：
1、正如我们所看到的， 如果没有额外的限制条件(在结点处要收费，费用不足还不给过)，那么， 这个问题就和经典的迪杰斯特拉问题一样了(找到两结点间的最短路径)。
2、在经典的迪杰斯特拉问题中， 我们使用一个一维数组来保存从开始结点到每个结点的最短路径的长度， 即M[i]表示从开始结点到结点i的最短路径的长度。然而在这个问题中， 我们还要保存我们身上剩余多少钱这个信息。因此，很自然的， 我们将一维数组扩展为二维数组。M[i][j]表示从开始结点到结点i的最短路径长度， 且剩余j元。
3、通过这种方式，我们将这个问题规约到原始的路径寻找问题。 在每一步中，对于已经找到的最短路径，我们找到它所能到达的下一个未标记状态(i,j)， 将它标记为已访问(之后不再访问这个结点)，并且在能到达这个结点的各个最短路径中， 找到加上当前边权重值后最小值对应的路径，即为该结点的最短路径。 (写起来真是绕，建议画个图就会明了很多)。不断重复上面的步骤， 直到所有的结点都访问到为止(这里的访问并不是要求我们要经过它， 比如有个结点收费很高，你没有足够的钱去经过它，但你已经访问过它) 最后Min[N-1][j]中的最小值即是问题的答案(如果有多个最小值， 即有多条最短路径，那么选择j最大的那条路径，即，使你剩余钱数最多的最短路径)。
-
源码:
import java.util.*;
public class NoPointerChartWithMoney {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int money = sc.nextInt();
int E = sc.nextInt();
Set<Integer> unVisited = new HashSet<>(N); //记录未访问节点
Set<Integer> visitied = new HashSet<>(N); //记录已经访问的节点
int[] M = new int[N]; //记录每个节点的过路费
int[][] V = new int[N][N]; //记录每条边的权重，初始值为0代表没有边
int[][] MIN = new int[N][money+1]; //记录从第一个节点到第i个节点还剩j元时的最短路径
List<Integer>[][] MIN_line = new List[N][money+1];
for(int i=0;i<N;i++){
for(int j=0;j<money+1;j++){
MIN[i][j]=999;
}
}
MIN[0][money]=0;
MIN_line[0][money] = new ArrayList<>();
MIN_line[0][money].add(0);
for(int i=0;i<N;i++){
M[i]=sc.nextInt();
}
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
V[i][j]=Integer.MAX_VALUE;
}
}
for(int i=0;i<E;i++){
int v1 = sc.nextInt();
int v2 = sc.nextInt();
int v = sc.nextInt();
V[v1][v2] = v;
V[v2][v1] = v;
}
for(int i=1;i<N;i++){
unVisited.add(i);
}
visitied.add(0);
int choice = 0; //中间节点下标，每次选出当前结点到所有可达未标记结点的最短路径端点为中间结点下标
while (unVisited.size() > 0) { //当仍然有未标记结点的时候
int tempMin = Integer.MAX_VALUE; //记录从中间节点到所有可达结点中的最小值（最短路径）
int tempMinI = -1; //记录最短路径的端点下标
Iterator<Integer> iti = unVisited.iterator();
while (iti.hasNext()) { //对于所有未标记的结点
int i = iti.next();
if (V[choice][i] != Integer.MAX_VALUE) { //如果中间结点到此未标记结点有边
for(int j=0;j<=money;j++) {
if(MIN[choice][j]!=999&&j-M[i]>0) {
if (MIN[i][j-M[i]] > V[choice][i] + MIN[choice][j]) { //计算中间结点到当前结点的最短路径
MIN[i][j - M[i]] = V[choice][i] + MIN[choice][j];
MIN_line[i][j-M[i]] = new ArrayList<>(MIN_line[choice][j]);
MIN_line[i][j-M[i]].add(i);
}
if (MIN[i][j-M[i]] < tempMin) { //计算当前结点到所有可达未标记结点的最短路径
tempMin = MIN[choice][j];
tempMinI = i;
}
}
}
}
}
unVisited.remove(tempMinI);visitied.add(tempMinI); //将当前结点记录未已经标记
choice = tempMinI; //重新定位中间结点
}
// 5 100 6
// 11 20 5 32 18
// 0 2 1
// 0 3 2
// 3 4 6
// 1 2 4
// 1 3 5
// 1 4 3
//打印最终的MIN数组
for(int j=0;j<money+1;j++){
System.out.print(j+"\t");
}
System.out.println();
for(int i=0;i<N;i++){
for(int j=0;j<money+1;j++){
if(MIN[i][j]!=999)
System.out.print(MIN[i][j]+"\t");
else
System.out.print(" "+"\t");
}
System.out.println();
}
int tempMin = 999;
int tempMinj = 0;
for(int j=0;j<=money;j++){
if(MIN[N-1][j]!=999){
if(MIN[N-1][j]<=tempMin) { //这里用小于等于会自动挑选剩余钱数最多的最短路径
tempMin = MIN[N - 1][j];
tempMinj = j;
}
}
}
System.out.println(tempMin+" "+tempMinj); //打印最短路径长度和剩余的钱数
Iterator<Integer> it = MIN_line[N-1][tempMinj].iterator(); //打印最短路径
System.out.print(it.next());
while (it.hasNext()){
System.out.print("->"+it.next());
}
System.out.println();
}
}
参考 http://www.hawstein.com/posts/dp-novice-to-advanced.html
参考 http://www.cnblogs.com/biyeymyhjob/archive/2012/07/31/2615833.html
参考 http://www.jianshu.com/p/b82de5ceca78
