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

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

二、思路阐述
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());
}

/**
* @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;

/**
* Initialises the edge with two vertices
* @param a - The vertex to connect the edge to.
* @param b - The vertex to connect the edge to.
*/
public Edge(Vertex a, Vertex b, int lifetime) {
this.a = a;
this.b = b;
}

/**
* ***DO NOT CHANGE***
* ToString method, allows the edge to be printed in the results.
* @return String representation of the edge.
*/
public String toString() {
}

/**
* Gets the lifetime of the edge.
* @return - The lifetime of the edge.
*/
}

/**
* 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;
}
}

import com.sun.deploy.util.ArrayUtil;
import org.omg.IOP.CodeSets;

import java.util.*;

/**
*
* 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
*/
public class LifetimeGraph implements GraphInterface {

/**
* Initialises the grpah with an empty adjacency list.
*/
}

/**
* 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
*
* @param a: Vertex A ID
* @param b: Vertex B ID
*/
@Override
//如果a不存在，创建a
if(vertex_a == null) {
vertex_a = new Vertex(a);
}
//如果b不存在，创建b
if(vertex_b == null) {
vertex_b = new Vertex(b);
}
Edge edgeTo = vertex_a.getEdgeTo(vertex_b);
if(edgeTo == null) {
} else {
}
}
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() {
Integer[] integers = setToArray(set);
int i = 0;
for(i = 0; i < integers.length; i++) {
int node = integers[i];
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) {
}
}
}

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) {

}

//采用递归的方法进行枚举，由于是递归，所以是深度优先遍历，但是遍历的过程中要检测结点是否已经被加入了路径当中
if(node == end) {//当遇到要达到的那个结点时，递归就结束了，只需要把路径加入到所有路径的list中
} else {
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;
}
}
}
}
//这个方法用来查找所有路径中最长的那一条
while (iterator.hasNext()) {
//            int sum = -1 >>> 1;
int sum = 0;
//往下的代码很简单，就是计算出该路径的长度，判断是否是最长的
Integer pop = next.pop();
while(!next.isEmpty()) {
Integer pop1 = next.pop();
pop = pop1;
}
//                if(sum > maxLifeTime || max.size() > next2.size()) {
max = next2;
}
}

Edge[] edges = new Edge[max.size()-1];
int i = 0;
Integer pop = max.pop();
while(!max.isEmpty()) {
Integer pop1 = max.pop();
pop = pop1;
edges[i++] = edgeTo;
}

return edges;
}

}

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

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

public class Main {
public static void main(String[] args) {
/**
*  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
*/
for (int i = 0; i < edges.length; i++) {
System.out.println(edges[i]);
}
}
}

最后输出的结果如下：

三、程序分析
但是其实非常好改进，只需要替换下面这段代码就行：改进的思路就是

一条路径的最大生存时间由该路径中lifetime最小的那条edge来决定

    private Edge[] findMaxLifeTimePath(LinkedList<LinkedList<Integer>> allPaths) {
while (iterator.hasNext()) {
int sum = -1 >>> 1;
//            int sum = 0;
//往下的代码很简单，就是计算出存活时间最长的路径
Integer pop = next.pop();
while(!next.isEmpty()) {
Integer pop1 = next.pop();
pop = pop1;
}
if (sum > maxLifeTime || max.size() > next2.size()) {
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) {
}

void dfs(int node, ArrayList<Integer> adj[], int dp[], boolean visited[]) {
// 标记访问过的结点
visited[node] = true;

// 遍历所有子节点
for (int i = 0; i < adj[node].size(); i++) {

// 如果没有访问过

// 存储最长路径
dp[node] = Math.max(dp[node], 1 + dp[adj[node].get(i)]);
}
}

// 返回最长路径
int findLongestPath(int n) {
// 开辟DP数组
int[] dp = new int[n + 1];

//访问数组来确认之前的结点是否被访问过
boolean[] visited = new boolean[n + 1];

// 对没有访问过的结点采用DFS算法
for (int i = 1; i <= n; i++) {
if (!visited[i])
}

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.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 : ...
• 1.DAG最短路（基于拓扑排序优化的Dijkstra算法） 拓扑排序给予了我们查找顺序的正确性,也减少了不必要的查找. （1）先对路径长度数组初始化，源点为0，其余为无穷大（这里用100000代替）。 （2）对图进行遍历，...
• 对于有向无，下面这种基于Dijkstra和拓扑排序的算法可以在线性时间内解决单点最短路径问题，且能够处理负权重的边，甚至能够求出最长路径。 该算法的思想很简单：按照拓扑顺序放松顶点。因为每条边v→w都只会被...
• 对于一个有向无，将至少存在一个入度为0的结点。显然，若不存在的话这将是一个有环。同时，最长路径的起点一定是入度为0的结点，我们就可以把所有入度为0的结点的far值设为0。入度不为0的far都设-1（方便起见...
• 关于最短距离算法最多莫过于Dijkstra算法。... 书上讲的Dijkstra算法看的不太懂，大致的意思是扩散求值的算法，即从源节点一步一步求最短路径的方法。即先找到源节点到其子节点的最短距离，然后再找源节点到其二级孙级
• 先看看此篇博客，了解常规floyd算法是如何求最短路径的，搞懂D和R的意义，再往后看，否则看不懂 https://blog.csdn.net/kabuto_hui/article/details/82886826 要求所有最短路径，其实很简单。 不管有几条最短路径，...
• 在一般的中，最长路径问题不具有如最短问题一样的最优子结构属性（算法导论动态规划章节P218） 在最长路径问题中，子问题是相关的 求解一个子问题会对另一个子问题产生影响 在最短路径问题中，子问题是无关的 ...
• 算法说明 先对图进行拓扑排序，再从入度的节点开始计算 dilg(v)=max(u,v)∈E{dilg(u)+w(u, v)} 源代码 #include <cstdio> #include <cstring> #include <vector> #include <queue> using ...
• 对于一般的，求最长路径并不最短路径那样容易，因为最长路径并没有最优子结构的属性。实际上求最长路径属于NP-Hard问题。然而，对于有向无最长路径问题有线性时间的解。思路
• 求最短路径问题，即从一点到另外一点的最短路径，Dijkstra算法即可解决，时间复杂度O(n^2) 在最短路都多条的情况下，求最少花费，加个判断条件即可   for(int i=1;i;i++) { if(dis[i]==dis[u]+g[u]...

...