如【0.2.5.6.8.9】88
【0.1.4.8.9】92
【0.1.2.5.7.9】56
。。。。。。。。。。。。。
即从源节点0到目的节点9 经过2..5.6.8节点 总权值为88
以此类推
10 个解决方案
#1
请各位不吝赐教,小妹感激不尽!!!
帮忙啊
帮忙啊
#2
楼主去看下深度或广度遍历
#3
遍历算法都能搞定这个问题,自己尝试下
#4
我知道要用深度或广度遍历,但自己要编有点困难,想的挺好,写时就不回了,由于要用java写代码,我才看了几天java书,要写代码还不太行。。希望哪位高手动动手帮个忙吧 ,我有急用,不然我就自己学java慢慢编了
对了这个是不是要深度优先结合回溯法才能搞定呢?
大家指教!
对了这个是不是要深度优先结合回溯法才能搞定呢?
大家指教!
#5
答:问题不大清楚啊。若清楚则就好写了。是源点与目的点之间所有的路径吗?中间若有个回路,则可是无限多条啊。是不是中间不能有回路啊?只能是没有回路的所有的简单路径啊?
#6
谢谢楼上的回答,
图是有向加权图,要求路径没有回路,不形成环,是没有回路的简单路径
请帮帮忙 我着急用,但自己java刚学,写代码费劲 谢谢
图是有向加权图,要求路径没有回路,不形成环,是没有回路的简单路径
请帮帮忙 我着急用,但自己java刚学,写代码费劲 谢谢
#7
答:参考代码与运行结果如下:
import java.util.*;
public class Graph {
//有向带权图。-1表示无路可通。自己到自己也是-1。其它表示权值。
private static int[][] graph=
{
{-1,2,3,3},
{-1,-1,-1,2},
{-1,2,-1,3},
{-1,-1,-1,-1}
};
private static boolean[] hasFlag=new boolean[graph.length];
//true-表示该结点已访问过。false-表示还没有访问过。
private static ArrayList<String> res=new ArrayList<String>();
//最后的所有的路径的结果。每一条路径的格式是如:0->2->1->3:7
//求在图graph上源点s到目标点d之间所有的简单路径,并求出路径的和。
public static void getPaths(int s,int d,String path,int sum)
{
hasFlag[s]=true;//源点已访问过.
for(int i=0;i<graph.length;i++)
{
if (graph[s][i]==-1 || hasFlag[i]){continue;}
//若无路可通或已访问过,则找下一个结点。
if(i==d)//若已找到一条路径
{
res.add(path+"->"+d+":"+(sum+graph[s][i]));//加入结果。
continue;
}
getPaths(i, d, path+"->"+i, sum+graph[s][i]);//继续找
hasFlag[i]=false;
}//for(i)
}
public static void main(String[] args) {
// TODO Auto-generated method stub
getPaths(0, 3, ""+0, 0);//从源点:0 到目点:3,初始路径:"0" 初始和:0
for(String e:res)//打印所有的结果
{
System.out.println(e);
}
}
}
运行结果:
0->1->3:4
0->2->1->3:7
0->2->3:6
0->3:3
#8
楼上人真好,我加你为好友了,希望以后能多指教,我QQ:470171029,能加我以后可能还会麻烦你,你不介意吧?
真的很感谢你,谢谢!
真的很感谢你,谢谢!
#9
答:不介意。不用谢。我也加你的QQ为好友了。共同讨论,互相学习提高。
#10
谢谢大家的关注和支持,o(∩_∩)o...
#1
请各位不吝赐教,小妹感激不尽!!!
帮忙啊
帮忙啊
#2
楼主去看下深度或广度遍历
#3
遍历算法都能搞定这个问题,自己尝试下
#4
我知道要用深度或广度遍历,但自己要编有点困难,想的挺好,写时就不回了,由于要用java写代码,我才看了几天java书,要写代码还不太行。。希望哪位高手动动手帮个忙吧 ,我有急用,不然我就自己学java慢慢编了
对了这个是不是要深度优先结合回溯法才能搞定呢?
大家指教!
对了这个是不是要深度优先结合回溯法才能搞定呢?
大家指教!
#5
答:问题不大清楚啊。若清楚则就好写了。是源点与目的点之间所有的路径吗?中间若有个回路,则可是无限多条啊。是不是中间不能有回路啊?只能是没有回路的所有的简单路径啊?
#6
谢谢楼上的回答,
图是有向加权图,要求路径没有回路,不形成环,是没有回路的简单路径
请帮帮忙 我着急用,但自己java刚学,写代码费劲 谢谢
图是有向加权图,要求路径没有回路,不形成环,是没有回路的简单路径
请帮帮忙 我着急用,但自己java刚学,写代码费劲 谢谢
#7
答:参考代码与运行结果如下:
import java.util.*;
public class Graph {
//有向带权图。-1表示无路可通。自己到自己也是-1。其它表示权值。
private static int[][] graph=
{
{-1,2,3,3},
{-1,-1,-1,2},
{-1,2,-1,3},
{-1,-1,-1,-1}
};
private static boolean[] hasFlag=new boolean[graph.length];
//true-表示该结点已访问过。false-表示还没有访问过。
private static ArrayList<String> res=new ArrayList<String>();
//最后的所有的路径的结果。每一条路径的格式是如:0->2->1->3:7
//求在图graph上源点s到目标点d之间所有的简单路径,并求出路径的和。
public static void getPaths(int s,int d,String path,int sum)
{
hasFlag[s]=true;//源点已访问过.
for(int i=0;i<graph.length;i++)
{
if (graph[s][i]==-1 || hasFlag[i]){continue;}
//若无路可通或已访问过,则找下一个结点。
if(i==d)//若已找到一条路径
{
res.add(path+"->"+d+":"+(sum+graph[s][i]));//加入结果。
continue;
}
getPaths(i, d, path+"->"+i, sum+graph[s][i]);//继续找
hasFlag[i]=false;
}//for(i)
}
public static void main(String[] args) {
// TODO Auto-generated method stub
getPaths(0, 3, ""+0, 0);//从源点:0 到目点:3,初始路径:"0" 初始和:0
for(String e:res)//打印所有的结果
{
System.out.println(e);
}
}
}
运行结果:
0->1->3:4
0->2->1->3:7
0->2->3:6
0->3:3
#8
楼上人真好,我加你为好友了,希望以后能多指教,我QQ:470171029,能加我以后可能还会麻烦你,你不介意吧?
真的很感谢你,谢谢!
真的很感谢你,谢谢!
#9
答:不介意。不用谢。我也加你的QQ为好友了。共同讨论,互相学习提高。
#10
谢谢大家的关注和支持,o(∩_∩)o...