精华内容
下载资源
问答
  • 无向有环最长路径算法

    千次阅读 2019-05-06 21:03:34
    前两天一个学金融的小伙伴找我帮忙写计算机课的作业,因为英语不好,以为是让求两点间的最大路径,之前自己实现过dijkstra算法,觉得可能不难就答应了。但是只想到了用穷举法枚举出所有路径的笨方法 二、思路...

    一、问题描述

    前两天一个学金融的小伙伴找我帮忙写计算机课的作业,因为英语不好,以为是让求两点间的最大路径,之前自己实现过dijkstra算法,觉得可能不难就答应了。但是只想到了用穷举法枚举出所有路径的笨方法

    问题描述

    二、思路阐述

          既然是图,就要先把图的关系表示出来,咱们用Vertex.java来表示结点,结点维护着与它相连的边,Edge.java来表示边,GraphInterface接口来规范一些模板方法。LifetimeGraph.java来实现具体查找最长路径的代码。在LifetimeGraph中,首先是添加结点和边的方法,然后是查找两点间最大路径的方法。该方法先找出两点间的所有路径,使用了递归,然后在所有路径中找出最长的。

     Vertex.java:

    import java.util.HashMap;
    
    /**
     * Vertex Class
     *
     * A vertex in the graph.
     * Stores the id of the vertex and the edges.
     *
     * Eg. if this is Vertex1 and it connects to Vertex2
     * this.edges[2] == edge between V1 and V2.
     */
    
    /**
     * The vertex class holds the "id" of the vertex and the
     * edges connected.
     *
     * To be inserted into the graph.
     */
    public class Vertex {
        private int id;
        private HashMap<Integer, Edge> edges;
    
        /**
         * Initialises the vertex and the empty set of edges.
         * @param id: the vertex ID.
         */
        public Vertex(int id) {
            this.id = id;
            this.edges = new HashMap<>();
        }
    
        /**
         * Get the vertex ID.
         * @return - The id of the vertex.
         */
        public int getId() {
            return this.id;
        }
    
        /**
         * Return the edges for this node.
         * @return: The map of edges for this node.
         */
        public HashMap<Integer, Edge> getEdges() {
            return this.edges;
        }
    
        /**
         * Return the edge from this vertex to the given
         * vertex if exists.
         * @param v (Vertex class) - The destination for the edge.
         * @return: The edge to the vertex or null. 
         */
        public Edge getEdgeTo(Vertex v) {
            return this.edges.get(v.getId());
        }
    
        /**
         * Add the edge to the "Adjacency List"
         * @param v: The vertex this edge is connected to.
         * @param e: The edge between this vertex and the given vertex.
         */
        public void addEdge(Vertex v, Edge e) {
            this.edges.put(v.getId(), e);
        }
    }
    

    Edge.java

    /**
     * Edge Class
     *
     * Provides the "lifetime" between two vertices
     * that are in a graph.
     */
    
    
    /**
     * Edge class holds the lifetime between two vertices.
     */
    public class Edge {
    
    
        private Vertex a;
        private Vertex b;
        private int lifetime;
    
        /**
         * Initialises the edge with two vertices
         * @param a - The vertex to connect the edge to.
         * @param b - The vertex to connect the edge to.
         * @param lifetime - The lifetime between two vertices
         */
        public Edge(Vertex a, Vertex b, int lifetime) {
            this.a = a;
            this.b = b;
            this.lifetime = lifetime;
        }
    
        /**
         * ***DO NOT CHANGE***
         * ToString method, allows the edge to be printed in the results.
         * @return String representation of the edge.
         */
        public String toString() {
            return String.format("V%s-%d-V%s", this.a.getId(), this.lifetime, this.b.getId());
        }
    
        /**
         * Gets the lifetime of the edge.
         * @return - The lifetime of the edge.
         */
        public int getLifetime() {
            return lifetime;
        }
    
        /**
         * Return the vertex A of the edge.
         * @return vertex A
         */
        public Vertex getA() {
            return a;
        }
    
        /**
         * Return the vertex B of the edge.
         * @return vertex B
         */
        public Vertex getB() {
            return b;
        }
    }
    

    LifetimeGraph.java

    import com.sun.deploy.util.ArrayUtil;
    import org.omg.IOP.CodeSets;
    
    import java.util.*;
    
    /**
     * Lifetime Graph
     *
     * Holds a graph of vertices where the edges between vertices has a lifetime.
     * The graph is implemented using an adjacency list.
     */
    
    /**
     * The lifetime graph to implement.
     *
     * Implement the methods for adding an edge, getting the edge set and
     * finding the lifetime path.
     */
    public class LifetimeGraph implements GraphInterface {
    
        private HashMap<Integer, Vertex> adjacencyList;
    
        /**
         * Initialises the grpah with an empty adjacency list.
         */
        public LifetimeGraph() {
            this.adjacencyList = new HashMap<>();
        }
    
        /**
         * Add an edge to the graph between the given vertices (a, b)
         *
         *
         * If the vertex doesn't exist, then create the vertex and add it to
         * the adjacency list.
         *
         * @param a: Vertex A ID
         * @param b: Vertex B ID
         * @param lifetime:  Lifetime of the edge.
         */
        @Override
        public void addEdge(int a, int b, int lifetime) {
            Vertex vertex_a = adjacencyList.get(a);
            Vertex vertex_b = adjacencyList.get(b);
            //如果a不存在,创建a
            if(vertex_a == null) {
                vertex_a = new Vertex(a);
                adjacencyList.put(a, vertex_a);
            }
            //如果b不存在,创建b
            if(vertex_b == null) {
                vertex_b = new Vertex(b);
                adjacencyList.put(b, vertex_b);
            }
            Edge edgeTo = vertex_a.getEdgeTo(vertex_b);
            if(edgeTo == null) {
                vertex_a.addEdge(vertex_b, new Edge(vertex_a, vertex_b, lifetime));
                vertex_b.addEdge(vertex_a, new Edge(vertex_b, vertex_a, lifetime));
            } else {
                edgeTo.setLifetime(lifetime);
            }
        }
        private Integer[] setToArray(Set<Integer> values) {
            Iterator<Integer> iterator1 = values.iterator();
            Integer[] integers = new Integer[values.size()];
            int i = 0;
            while(iterator1.hasNext()) {
                integers[i] = iterator1.next();
                i++;
            }
            Arrays.sort(integers);
    
            return integers;
        }
        /**
         * Return the set of edges in the graph
         *
         * The edges should be returned in order of vertices,
         * e.g. loop through vertices from 0-N.
         *
         * @return: List of edges in the graph.
         */
        @Override
        public Edge[] edges() {
            Set<Integer> set = adjacencyList.keySet();
            Integer[] integers = setToArray(set);
            int i = 0;
            LinkedList<Edge> linkedList = new LinkedList<>();
            for(i = 0; i < integers.length; i++) {
                int node = integers[i];
                Vertex vertex = adjacencyList.get(node);
                HashMap<Integer, Edge> edges = vertex.getEdges();
                Set<Integer> integers1 = edges.keySet();
                Integer[] integers2 = setToArray(integers1);
                for(int j = 0; j < integers2.length; j++) {
                    if(integers2[j] > node) {
                        linkedList.addLast(vertex.getEdgeTo(adjacencyList.get(integers2[j])));
                    }
                }
            }
            Edge[] edges1 = linkedList.toArray(new Edge[linkedList.size()]);
    
            return edges1;
        }
    
        /**
         * Return a maximum lieftime path between two vertices.
         *
         * @param start: (int) The ID of vertex A to begin the path.
         * @param end: (int) The ID of vertex B to end the path.
         * @return: The list of edges that create the path.
         */
        @Override
        public Edge[] lifetimePath(int start, int end) {
            LinkedList<LinkedList<Integer>> allPaths = new LinkedList<>();
            LinkedList<Integer> list = new LinkedList<>();
            addPath(allPaths, list, start, end);
    
            return findMaxLifeTimePath(allPaths);
        }
    
        //采用递归的方法进行枚举,由于是递归,所以是深度优先遍历,但是遍历的过程中要检测结点是否已经被加入了路径当中
        public void addPath(LinkedList<LinkedList<Integer>> allPaths, LinkedList<Integer> path, Integer node, Integer end) {
            path.add(node);//当前的path包含着根节点,即起点,path还有一个作用,就是用来检测下一个要加入的结点在路径中是否已经包含
            if(node == end) {//当遇到要达到的那个结点时,递归就结束了,只需要把路径加入到所有路径的list中
                allPaths.add(path);
            } else {
                Vertex vertex = adjacencyList.get(node);
                HashMap<Integer, Edge> edges = vertex.getEdges();
                Set<Integer> integers = edges.keySet();
                Iterator<Integer> iterator = integers.iterator();
                while (iterator.hasNext()) {
                    Integer next = iterator.next();
                    if(path.contains(next)) {
                        continue;
                    }
                    addPath(allPaths, new LinkedList<>(path), next, end);
                }
            }
        }
        //这个方法用来查找所有路径中最长的那一条
        private Edge[] findMaxLifeTimePath(LinkedList<LinkedList<Integer>> allPaths) {
            Iterator<LinkedList<Integer>> iterator = allPaths.iterator();
            LinkedList<Integer> max = null;
            int maxLifeTime = 0;
            while (iterator.hasNext()) {
    //            int sum = -1 >>> 1;
                int sum = 0;
                LinkedList<Integer> next = iterator.next();
                LinkedList<Integer> next2 = new LinkedList<>();
                next2.addAll(next);//不修改原有创建好的路径
                //往下的代码很简单,就是计算出该路径的长度,判断是否是最长的
                Integer pop = next.pop();
                while(!next.isEmpty()) {
                    Integer pop1 = next.pop();
                    Vertex vertex = adjacencyList.get(pop);
                    Edge edgeTo = vertex.getEdgeTo(adjacencyList.get(pop1));
                    int lifetime = edgeTo.getLifetime();
                    sum  += lifetime;
                    pop = pop1;
                }
                if(sum > maxLifeTime) {
    //                if(sum > maxLifeTime || max.size() > next2.size()) {
                        maxLifeTime = sum;
                        max = next2;
                }
            }
    
            Edge[] edges = new Edge[max.size()-1];
            int i = 0;
            Integer pop = max.pop();
            while(!max.isEmpty()) {
                Integer pop1 = max.pop();
                Vertex vertex = adjacencyList.get(pop);
                Edge edgeTo = vertex.getEdgeTo(adjacencyList.get(pop1));
                pop = pop1;
                edges[i++] = edgeTo;
            }
    
            return edges;
        }
    
    
    }
    

     测试:咱们就用这个例子来测试

    先手动构建出来这个图表达的关系:

     

    public class Main {
        public static void main(String[] args) {
            LifetimeGraph lifetimeGraph = new LifetimeGraph();
            /**
             *  V0-1-V1  V0-2-V2  V0-6-V3  V0-1-V4  V0-1-V5
             *  V0-1-V6  V0-1-V7  V1-8-V2  V1-5-V7  V2-8-V3
             *  V3-8-V4  V4-8-V5  V5-8-V6  V6-8-V7
             */
            lifetimeGraph.addEdge(0, 1, 1);
            lifetimeGraph.addEdge(0, 2, 2);
            lifetimeGraph.addEdge(0, 3, 6);
            lifetimeGraph.addEdge(0, 4, 1);
            lifetimeGraph.addEdge(0, 5, 1);
            lifetimeGraph.addEdge(0, 6, 1);
            lifetimeGraph.addEdge(0, 7, 1);
            lifetimeGraph.addEdge(1, 2, 8);
            lifetimeGraph.addEdge(1, 7, 5);
            lifetimeGraph.addEdge(2, 3, 8);
            lifetimeGraph.addEdge(3, 4, 8);
            lifetimeGraph.addEdge(4, 5, 8);
            lifetimeGraph.addEdge(5, 6, 8);
            lifetimeGraph.addEdge(6, 7, 8);
            Edge[] edges = lifetimeGraph.lifetimePath(6, 4);
            for (int i = 0; i < edges.length; i++) {
                System.out.println(edges[i]);
            }
        }
    }
    

    最后输出的结果如下:

     

    三、程序分析

    其实最后我同学告诉我理解错了题意,这个题不是求两点间的最长路径,而是求两点间生存时间最长的一条路径,lifetime不是距离,而是当前这条edge能够存在的时间。

    但是其实非常好改进,只需要替换下面这段代码就行:改进的思路就是

    一条路径的最大生存时间由该路径中lifetime最小的那条edge来决定
        private Edge[] findMaxLifeTimePath(LinkedList<LinkedList<Integer>> allPaths) {
            Iterator<LinkedList<Integer>> iterator = allPaths.iterator();
            LinkedList<Integer> max = null;
            int maxLifeTime = 0;
            while (iterator.hasNext()) {
                int sum = -1 >>> 1;
    //            int sum = 0;
                LinkedList<Integer> next = iterator.next();
                LinkedList<Integer> next2 = new LinkedList<>();
                next2.addAll(next);//不修改原有创建好的路径
                //往下的代码很简单,就是计算出存活时间最长的路径
                Integer pop = next.pop();
                while(!next.isEmpty()) {
                    Integer pop1 = next.pop();
                    Vertex vertex = adjacencyList.get(pop);
                    Edge edgeTo = vertex.getEdgeTo(adjacencyList.get(pop1));
                    int lifetime = edgeTo.getLifetime();
                    sum  = sum > lifetime ? lifetime : sum;//一条路径的最大生存时间由该路径中lifetime最小的那条edge来决定
                    pop = pop1;
                }
                if(sum >= maxLifeTime) {
                    if (sum > maxLifeTime || max.size() > next2.size()) {
                        maxLifeTime = sum;
                        max = next2;
                    }
                }
            }
    

     

    自我感觉非常差劲,像老太太的裹脚布一样又臭又长,但是想了好久没有想到如何用栈来替代递归。

    希望大家在评论区给出一些指导性的意见。

    展开全文
  • 寻找有向环图中的最长路径(JAVA+动态规划) 给出了一个具有n个顶点和m个边的有向图G。任务是找出图中最长有向路径的长度。 注:有向路径的长度是指路径中的边数。 例如:下图中有4个顶点,5条边。 最长的有...

    寻找有向无环图中的最长路径(JAVA+动态规划)

    给出了一个具有n个顶点和m个边的有向图G。任务是找出图中最长有向路径的长度。

    注:有向路径的长度是指路径中的边数。

    例如:下图中有4个顶点,5条边。

    最长的有向路径的长度为 3。

    从1到3,到2,到4。


    算法实现

    package com.bean.algorithm.graph;
    
    import java.util.ArrayList;
    
    public class LongestPathDirectedAcyclicGraph {
    	
    	int vertices;
    	ArrayList<Integer> edge[];
    
    	LongestPathDirectedAcyclicGraph(int vertices) {
    		this.vertices = vertices;
    		edge = new ArrayList[vertices + 1];
    		for (int i = 0; i <= vertices; i++) {
    			edge[i] = new ArrayList<>();
    		}
    	}
    
    	void addEdge(int a, int b) {
    		edge[a].add(b);
    	}
    
    	void dfs(int node, ArrayList<Integer> adj[], int dp[], boolean visited[]) {
    		// 标记访问过的结点
    		visited[node] = true;
    
    		// 遍历所有子节点
    		for (int i = 0; i < adj[node].size(); i++) {
    
    			// 如果没有访问过
    			if (!visited[adj[node].get(i)])
    				dfs(adj[node].get(i), adj, dp, visited);
    
    			// 存储最长路径
    			dp[node] = Math.max(dp[node], 1 + dp[adj[node].get(i)]);
    		}
    	}
    
    	// 返回最长路径
    	int findLongestPath(int n) {
    		ArrayList<Integer> adj[] = edge;
    		// 开辟DP数组
    		int[] dp = new int[n + 1];
    
    		//访问数组来确认之前的结点是否被访问过 
    		boolean[] visited = new boolean[n + 1];
    
    		// 对没有访问过的结点采用DFS算法
    		for (int i = 1; i <= n; i++) {
    			if (!visited[i])
    				dfs(i, adj, dp, visited);
    		}
    
    		int ans = 0;
    
    		// 遍历和寻找所有最大的dp[i]
    		for (int i = 1; i <= n; i++) {
    			ans = Math.max(ans, dp[i]);
    		}
    		return ans;
    	}
    
    	// Driver code
    	public static void main(String[] args) {
    		int n = 5;
    		LongestPathDirectedAcyclicGraph graph = new LongestPathDirectedAcyclicGraph(n);
    		// Example-1
    		graph.addEdge(1, 2);
    		graph.addEdge(1, 3);
    		graph.addEdge(3, 2);
    		graph.addEdge(2, 4);
    		graph.addEdge(3, 4);
    		graph.findLongestPath(n);
    		System.out.println(graph.findLongestPath(n));
    
    	}
    }
    

    程序运行结果:

    3

     

    展开全文
  • 无权无向图最长路径介绍 介绍 想啥呢,无权无向图哪有最长路径,怕是得死循环了Dog!

    无权无向图的最长路径

    介绍

    想啥呢,无权无向图哪有最长路径,怕是得死循环了Dog!

    展开全文
  • 最近在做最长路径的实验,

            最近在做求有向无环图的最长路径的问题,当然,求最长路径有许多方法,比如可以直接用Floyd算法来求,只需稍微改动一下,不过用拓扑排序+动态规划来做,百度搜索了一下,介绍这方面的资料不够完善,也许会让许多人不够清楚实现原理,在这里,我讲解一下自己的一些思路,分成四部分进行编程:


          一、创建有向无环图:

          我用的数据存储结构是邻接矩阵,如果用邻接表也是可以的。这里就不多作解释,直接进入关键代码部分。

            

          二、拓扑排序:

          官方解释是:对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序,是将G中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若边(u,v)∈E(G),则u在线性序列中出现在v之前。

          用通俗的话来讲就是,比如你要选课A、B、C,但是读B要先选A,读A要先选C,所以,进行拓扑排序后,就是C、A、B。

          所以在创建图的时候,要用一个标志数组indegree[]来保存每个顶点的入度,另外,在进行下面求最长路径的时候,需要用到拓扑排序的结果,所以还需要一个数组topo[]来记录拓扑排序的结果。

          拓扑排序里,都先找到入度为0的顶点,然后把它取出来(让它的入度等于负数进行实现),保存在topo[]里面,接着更新其他与这个顶点相邻的其他顶点的入度,最后,循环即可。

         

         三、求最长路径:

         只要知道了动态规划的公式就好,这里直接给出公式maxPath[v]=max{maxPaht[v],maxPath[k]+e[k][v]},其中maxPath[v]表示的是起始点到点v的最长路径,e[k][v]表示点k到点v的距离。这个公式的意思是,假如有A、B、C三个点,求maxPath[C],要么直接取maxPath[C],要么取maxPath[A]+e[A][C],要么取maxPath[B]+e[B][C]。当然,这个公式的所需要的顶点需要按顺序取自拓扑排序的结果,否则,有可能在进行求maxPath[k]+e[k][v]的时候,maxPath[k]并不是最长的,造成结果出错。

       

           四、求最长路线:

         这个我想了挺久的,最后想到的方法是用一个二维矩阵(N*N)保存每一个点到点的最长路径,对第N列进行排序,取出第N列中最大的一个数a,记录下行号R和列号C(在v1—>v2中,行对应的是v1,列对应的是v2),然后把列号C压进栈里(输出的时候直接输出就是最长路线了),接着按照这个数字a的行号R找到相同数字的列号R'(比如a数字在的位置是[4][5],行号是4,则找到第4列),令N=R‘,重复以上步骤即可。

         

        下面贴出源代码仅供参考:


        

    #include <iostream>
    #include <algorithm>
    #include <stack>
    using namespace std;
    
    char *v;//顶点数组,下标为顶点号,值为顶点名称(用在创建有向无环图中)
    int **e;//边的二维矩阵(用在创建有向无环图中)
    
    int *indegree;//保存顶点入度数的数组(求拓扑排序)
    int *topo;//保存拓扑排序结果的数组(求拓扑排序)
    
    int *maxPath;//保存到此点的最长路径(求最长路径)
    
    //创建有向无环图
    void creatGraph(int vSize,int eSize)
    {
    	//初始化
    	int i,j,k,c;
    	char a,b;
    	indegree=new int[vSize];
    	topo=new int[vSize];	
        v=new char[vSize];
    	e=new int*[vSize];
    	for(i=0;i<vSize;i++)
    		 e[i]=new int[vSize];
    	for(i=0;i<vSize;i++)
    		for(j=0;j<vSize;j++)
    			e[i][j]=0;
    	for(i=0;i<vSize;i++)
    	{
    		indegree[i]=0;
    		topo[i]=0;
    	}
    
    	//建图
    	cout<<endl<<"请输入各顶点名称:";
    	for(i=0;i<vSize;i++)
    		cin>>v[i];
    	cout<<endl<<"请先后输入顶点V1和V2(表示V1->V2)以及权值,按换行键继续"<<endl;
    	for(i=0;i<eSize;i++)
    	{
    	    cin>>a>>b>>c;
    		for(j=0;j<vSize;j++) 
    		   if(v[j]==a) break;
    		for(k=0;k<vSize;k++)
    		   if(v[k]==b) break;
    		   e[j][k]=c;
    		   indegree[k]++;//入度+1
    
    	}
    }
    
    //拓扑排序
    void topologicalSort(int vSize)
    {
    	int i,j,k;
    	for(i=0;i<vSize;i++) //vSize次循环
    	{
    		j=0;
    		while(j<vSize&&indegree[j]!=0) j++;//找到入度为0的顶点
    		topo[i]=j;//保存
    		indegree[j]=-1;// 设结点j为入度为-1,以免再次输出j
    		
    		for(k=0;k<vSize;k++)//更新其他入度点
    			if(e[j][k]!=0)
    				indegree[k]--;
    	}
    }
    
    //最长路径
    void getMaxPath(int vSize)
    {
    	//初始化
    	int i,j,k,v1,v2,max=0,**path,*p;
    	maxPath=new int[vSize];            //保存最长路径,表示到顶点N的最长路径
    	p=new int[vSize];                  //用来处理最长路线的选择顶点
        path=new int*[vSize];	           //用来保存点到点的最长路径矩阵
    	for(i=0;i<vSize;i++)
    		 path[i]=new int[vSize];
    	for(i=0;i<vSize;i++)
    		for(j=0;j<vSize;j++)
    			path[i][j]=0;
    	for(i=0;i<vSize;i++)
    	{   
    		maxPath[i]=0;
    		p[i]=0;		
    	}
    
    		//关键代码,求最长路径
    		for(j=0;j<vSize;j++)
    		{
    			v2=topo[j];
    			for(k=0;k<j;k++)
    			{
    				 v1=topo[k];
    	             if(e[v1][v2]!=0)                     //表示有路
                     {   
    					 if(maxPath[v1]+e[v1][v2]>maxPath[v2])
    		                maxPath[v2]=maxPath[v1]+e[v1][v2];
    
    				     if(maxPath[v2]>max)
    					 {
    				        max=maxPath[v2];//保存长度
    					    path[v1][v2]=max;									     
    					 }
    				 }
    			}					
    		}
    
    		//求最长路线
            stack<int> s;//保存线路
    		for(i=vSize-1;i>0;)
    		{
    			for(j=0;j<vSize;j++)
    			{
    				p[j]=path[j][i];  								
    			}
    			sort(p,p+vSize);
    			int maxValue=p[j-1];
    			if(maxValue!=0)  
    			{
    			    for(j=0;j<vSize;j++)
    				{
    				    if(path[j][i]==maxValue)
    					{
    					   s.push(i);
    					   i=j;
    				       if(i==0)
    						  s.push(i);
    					   break;
    					}  
    				}
    			}
    		}
    
    		//输出结果
    		cout<<endl<<"最长路径的长度是:"<<max<<endl<<"最长路径为:";
    		int len=s.size();
    		for(i=0;i<len;i++)
    		{
    			if(i!=0) cout<<" -> "; 
    			cout<<v[s.top()];
    	    	s.pop();
    		}		
    		cout<<endl<<endl;
    }
    
    int main()
    {
    	int vSize,eSize,i;
    	while(1)
    	{
    		cout<<"·请分别输入有向无环图的顶点数和边数:";
    		cin>>vSize>>eSize;
    
    	    creatGraph(vSize,eSize);//创建图
            topologicalSort(vSize);//拓扑排序
    		getMaxPath(vSize);//最长路径
    			
    	}
    	return 0;
    }
    

    欢迎大家交流~

        

         


        

          

            

    展开全文
  • 给定一个有向无$G=(V,E)$,边权重为实数,给定中的两个顶点$k,t$,设计动态规划算法,求从k到t的最长简单路径,子问题是怎样的?算法的效率如何?算法分析:该问题不能够用贪心求解,假设从k出发,每一步...
  • 将此作为参考,假设我想要0到5之间的最长路径。那将是:0-> 1-> 3-> 2-> 4-> 6-> 5有什么好的算法吗?我已经搜索过,却没有发现我能理解的任何东西。我已经找到了最短路径(0-> 1-> 2-> ...
  • 原标题:拓扑排序-有向无中的最长路径给定一个加权d irected (DAG)和一个源点s在它,找到从s中最长的距离在给定中的所有其他顶点。一般最长路径问题并不像最短路径问题那么容易,因为最长路径问题没有最优...
  • 将此图表作为参考,假设我想要0到5之间的最长路径.那将是:0-> 1-> 3-> 2-> 4-> 6-> 5对此有什么好的算法吗?我搜索过,但没有发现任何我能理解的内容.我已经找到了用于最短路径的大量算法(0-> 1...
  • 我用Dijkstra算法,写了一个无环有向图/无向图(多加一条相反的路径仅此而已) 的最短路径问题的解决方案。如果是无向图也很简单,把每个无向的edge拆开成两个有向的就可以解决了。为了每次弹出正确的端点,我也实现了...
  • 首先使用拓扑排序,然后从后往前对顶点计算最长路径。 转载:https://blog.csdn.net/weixin_42182525/article/details/98172071
  • 3.4 floyd算法(多源最短路径) 复杂度O(V^3) 初始矩阵为road[i][j],每次尝试将一点作为中间点,是否存在更短路径,若存在,则更新矩阵。 4.源码 本来以为样例通过了就OK,但实际算法有很多细节没敲对,比如INF没有...
  • 最长路径算法 图形中最短和最长路径算法的快速概述和比较。 关于图形中无辜的看起来最短和最长路径问题,有许多小点需要记住。 在计算机程序员的技术工作面试中,关于此主题的问题非常常见。 但是,通常很难保持...
  • # 环加权有向图的“最长路径”算法(含“负权重”边) ''' 思路:寻找的起点到各点的最长路径,其实修改最短路径算法AcyclicLP就可以得到 主要变化为:设把初始起点到各顶点的距离从“inf”变 "-inf"; 边松弛条件...
  • 1、ve数组的求解 ve:顶点(事件)的最早开始时间(时刻)。 //拓扑序列 stack<int> topOrder; //拓扑排序,顺便求ve数组 bool topologicalSort() { queue<... if(inDegree[...
  • EdgeWeightedDigraph.h #pragma once #include #include #include ...//求最长路径时将 > 改为 < ...//求最长路径时将 max() 改为 min() disTo[i] = std ::numeric_limits<T>::max(); } ...
  • 题解 这题一开始以为可以用dijkstra求解,但是实际上不行。原因在于最短路径问题中有最优子结构,即最短路径的子路径还是最短路径,...求出下面有向图中,顶点“5”到其他所有顶点的最长路径和长度。 输入 根据上面
  • 向无中的最长路径-PART1 给定一个加权有向无DAG和一个源点s在它,找到从s中最长的距离在给定中的所有其他顶点 一般最长路径问题不像最短路径问题那么容易,因为最长路径问题不具有最优子结构属性...
  • 输入: 4 6 1 2 10 2 3 20 3 4 30 4 1 40 1 3 50 2 4 60 输出: 150 代码如下: #include <iostream> using namespace std; int ans = -1; const int N = 25; int mp[N][N]; bool vis[N];...
  • 加权图最长路径问题是图论中一个重要的问题,可以通过动态规划的思想进行解决。 问题描述 给定一个有加权环图G,从G中找出入度的顶点s,求从s出发到其他顶点的最长路径。 下文源代码运行结果参照此图 ...
  • 这个一个无向图 这是上次算出的距离矩阵和路由矩阵,接下来介绍如何根据这个路由矩阵(元胞)写出所有最短路径 函数 function path=path_all(r, start, dest) % r : 路由表 % start : 起点index % dest : ...
  • 的最短路和最长路径

    千次阅读 2018-11-21 18:42:34
    1.DAG最短路(基于拓扑排序优化的Dijkstra算法) 拓扑排序给予了我们查找顺序的正确性,也减少了不必要的查找. (1)先对路径长度数组初始化,源点为0,其余为无穷大(这里用100000代替)。 (2)对图进行遍历,...
  • 向无的最短路径求解算法

    千次阅读 2018-10-29 21:45:34
    对于有向无,下面这种基于Dijkstra和拓扑排序的算法可以在线性时间内解决单点最短路径问题,且能够处理负权重的边,甚至能够求出最长路径。 该算法的思想很简单:按照拓扑顺序放松顶点。因为每条边v→w都只会被...
  • 对于一个有向无,将至少存在一个入度为0的结点。显然,若不存在的话这将是一个有环。同时,最长路径的起点一定是入度为0的结点,我们就可以把所有入度为0的结点的far值设为0。入度不为0的far都设-1(方便起见...
  • 无向图最短路径算法(C#)实现

    万次阅读 2012-05-09 00:37:14
    关于最短距离算法最多莫过于Dijkstra算法。... 书上讲的Dijkstra算法看的不太懂,大致的意思是扩散求值的算法,即从源节点一步一步求最短路径的方法。即先找到源节点到其子节点的最短距离,然后再找源节点到其二级孙级
  • 先看看此篇博客,了解常规floyd算法是如何求最短路径的,搞懂D和R的意义,再往后看,否则看不懂 https://blog.csdn.net/kabuto_hui/article/details/82886826 要求所有最短路径,其实很简单。 不管有几条最短路径,...
  • 在一般的中,最长路径问题不具有如最短问题一样的最优子结构属性(算法导论动态规划章节P218) 在最长路径问题中,子问题是相关的 求解一个子问题会对另一个子问题产生影响 在最短路径问题中,子问题是无关的 ...
  • 算法导论 · 动态规划 · DAG最长路径

    千次阅读 2019-07-26 23:16:37
    算法说明 先对图进行拓扑排序,再从入度的节点开始计算 dilg(v)=max(u,v)∈E{dilg(u)+w(u, v)} 源代码 #include <cstdio> #include <cstring> #include <vector> #include <queue> using ...
  • ACM 在有向无中求最长路径

    千次阅读 2017-09-09 16:29:18
    对于一般的,求最长路径并不最短路径那样容易,因为最长路径并没有最优子结构的属性。实际上求最长路径属于NP-Hard问题。然而,对于有向无最长路径问题有线性时间的解。思路
  • 无向图最短路径问题

    千次阅读 2018-11-19 23:51:05
    求最短路径问题,即从一点到另外一点的最短路径,Dijkstra算法即可解决,时间复杂度O(n^2) 在最短路都多条的情况下,求最少花费,加个判断条件即可   for(int i=1;i;i++) { if(dis[i]==dis[u]+g[u]...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 21,102
精华内容 8,440
关键字:

无向图最长路径算法