图的实现比较麻烦。。写一下思路。。个人思路，没写代码实现过，不知道对错，欢迎批评指正。
先将顶点排序，s放在第一个，t放在最后一个，中间假设分别是x1,x2,x3......，将他们存储到一个数组v[n]中
设置权重表w[][]，w[i][j]存储i到j的权重，初始化为原始图中v[i]到v[j]的权重，两点无有向路径初始化为负无穷，可以在O(E)时间内完成，其中E是图中有向边的数量，再初始化w[i][i]=0
再设置辅助表p[][]，记录每次取到最大值的位置
for int l=3 to n
{
for int i=1 to n-l+1
{
int j=i+l-1
for r = i+1 to j
{
t = w[i][r] + w[r][j]
if t>w[i][j]
{
w[i][j]=t
p[i][j]=r
}
}
}
}
这样就可以找到w[0][n]最大权值，根据辅助表p[][]，可以找出具体路径，这里略过。