求有向图中两点间（已知的源节点和目的节点）的所有路径怎么求啊

本人在做传感器网络路由方面的课题，遇到的问题是想找出加权有向图中两点间的所有路径，我看了下，现成的算法如dijstra等都是求最短路径的。。。没有求所有路径的，希望哪位高人能帮帮忙，实现一下，最好是java实现，要求列出所有的路径集合
如【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刚学，写代码费劲 谢谢 

#7

引用 6 楼 wxbpearl 的回复:

谢谢楼上的回答， 
图是有向加权图，要求路径没有回路，不形成环，是没有回路的简单路径 
  请帮帮忙  我着急用，但自己java刚学，写代码费劲 谢谢 

答：参考代码与运行结果如下：

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

引用 8 楼 wxbpearl 的回复:

楼上人真好，我加你为好友了，希望以后能多指教，我QQ：470171029，能加我以后可能还会麻烦你，你不介意吧？ 
真的很感谢你，谢谢！

答：不介意。不用谢。我也加你的QQ为好友了。共同讨论，互相学习提高。

#10

谢谢大家的关注和支持，o(∩_∩)o...