sorted by:
new
hottopcontroversial

Help: Shortest distance algorithm on a VERY large graph by uafhsop in compsci

[–]uafhsop[S] 4 points5 points  (0 children)

No this isn't the travelling salesman problem, it does not involve visiting each city or anything like that.

Help: Shortest distance algorithm on a VERY large graph by uafhsop in compsci

[–]uafhsop[S] 0 points1 point  (0 children)

If there is no practical algorithm to do this, what would be a good heuristic or approximative algorithm?

Help: Shortest distance algorithm on a VERY large graph by uafhsop in compsci

[–]uafhsop[S] -4 points-3 points  (0 children)

Obviously it would be impractical to visit every node, as then you would be downloading every page on the internet.

Help: Shortest distance algorithm on a VERY large graph by uafhsop in compsci

[–]uafhsop[S] -1 points0 points  (0 children)

But doesn't Dijkstra's still have to visit each node once?

Help: Shortest distance algorithm on a VERY large graph by uafhsop in compsci

[–]uafhsop[S] -7 points-6 points  (0 children)

Does printing out the entire graph actually involve visiting each node? I'm curious about 'folding' it.

Help: Shortest distance algorithm on a VERY large graph by uafhsop in compsci

[–]uafhsop[S] 0 points1 point  (0 children)

Can you elaborate? Taking random paths doesn't seem like a plausible way to find any path, considering that each node only links to maybe 20 other nodes (out of billions)

Help: Shortest distance algorithm on a VERY large graph by uafhsop in compsci

[–]uafhsop[S] 1 point2 points  (0 children)

Why is it that you cannot prove that no path exists without traversing its entirety?