询问关于一个矩阵算法相关的问题

smh821025 发布于 2015/04/15 23:06
阅读 173
收藏 0

各位,遇到一个算法的问题,想询问下大家,由于本人数据结构和算法方面不是很精通,请给一些相关提示,谢谢

有一个n*n的矩阵,需要从左向右进行节点连接,可以向上移动,向下移动,向右移动,最终形成一条链路。结果是要,求得所连起链路中包含元素的和,而且求得的Sum要求是所有可以经过元素链路最小的一个值。

比如:

49,2,80,20
50,1,199,100
60,10,1,1
88,12,1,19

最终的和是63,需要用java实现,请算法相关的高手给予一些提示,谢谢

加载中
0
来福的主人

这个如果n不大的话,并且对时间的要求不是很高,就可以建一个图,然后跑最短路径就可以得到了。

具体是:

如果点i可以移动到点j,那么就可以从点i到点j连一条边,权值为点j的值。

然后再建一个起始点,该点与所有最左边的点连接,权值为0。

最后建一个终止点,该点与所有最右边的点连接,权值为0。

这样,图就建成功了,然后跑从起点到终点的Dijkstra最短路径就可以求出来了。

返回顶部
顶部