|
Thread Rules
1. This is not a "do my homework for me" thread. If you have specific questions, ask, but don't post an assignment or homework problem and expect an exact solution.
2. No recruiting for your cockamamie projects (you won't replace facebook with 3 dudes you found on the internet and $20)
3. If you can't articulate why a language is bad, don't start slinging shit about it. Just remember that nothing is worse than making CSS IE6 compatible.
4. Use [code] tags to format code blocks. |
On June 06 2018 10:43 travis wrote:
cool stuff, thanks
new question, for the few of these that might know about this for some reason.
shortest paths algorithms seem to see a lot of research. particularly, all pairs shortest paths. I can find almost no research on all pairs *all* shortest paths, however. Is there any demand for such an algorithm? I don't see it being useful outside of unweighted graphs or specific types of weighted graphs... but I still see it being useful. I am surprised I could only find one paper on it. I have a couple algorithms I have made that do a pretty good job of finding this, but I am not sure anyone would even care. I've also made a fast all pairs shortest paths lengths algorithm.
I am familiar with say, all the algorithms referenced in wikipedia shortest paths article. But, I do not know any algorithms specialized to find shortest path lengths - or if there actually are any that are distinctly different from the ones that find paths.
another thing I have been working on is a dynamic shortest paths data structure, for updating all pairs shortest paths on edge additions or removals, instead of rerunning from scratch.
What's the difference between "all pairs shortest paths" and "all pairs *all* shortest paths"?
Floyd-Warshall gives the shortest paths and their lengths between all vertices in a graph. Maybe I'm not understanding your question.
(I realize you're probably well aware of this.)
|
for floyd warshall, it can easily be implemented to return all shortest paths, and it's strong for dense graphs. but it is pretty awful for sparse graphs.
djikstra's can be modified to return all shortest paths, but it becomes slower
but my question is about application of these algorithms in the real world. I know for example, GPS algorithms use shortest paths. but do they care about being able to find all of the shortest paths from A to B, or just one?
|
On June 06 2018 22:52 travis wrote:
for floyd warshall, it can easily be implemented to return all shortest paths, and it's strong for dense graphs. but it is pretty awful for sparse graphs.
djikstra's can be modified to return all shortest paths, but it becomes slower
but my question is about application of these algorithms in the real world. I know for example, GPS algorithms use shortest paths. but do they care about being able to find all of the shortest paths from A to B, or just one?
Don't have a background in comp sci, but how can you have more than 1 shortest path? 
edit: I suppose if you have paths of equal length, but what would be the application?
|
yeah, paths of equal length. in graphs with like, float weights or big weights with huge variance, it probably won't happen. but for graphs with simple weights it happens often, and most unweighted graphs have multiple shortest paths (sometimes an exponential amount of them).
I am not sure about the application! That's why I am asking .
I suppose it could be useful for routing algorithms to find alternate shortest paths in case a user doesn't like the current suggestion. I also think it has applications in other algorithms that are trying to solve more complicated problems.
|
On June 07 2018 00:42 travis wrote:yeah, paths of equal length. in graphs with like, float weights or big weights with huge variance, it probably won't happen. but for graphs with simple weights it happens often, and most unweighted graphs have multiple shortest paths (sometimes an exponential amount of them). I am not sure about the application! That's why I am asking . I suppose it could be useful for routing algorithms to find alternate shortest paths in case a user doesn't like the current suggestion. I also think it has applications in other algorithms that are trying to solve more complicated problems.
It seems like having multiple paths from point A to B depends on what successors you are returning for each vertex. This is an implementation choice. You can return successors using any criteria you see fit. This would change the way you would traverse the graph.
It also sounds like your exit criteria for graph search is different than normal exit criteria for graph search. The normal goal criteria are to exit when a path is found from source to sink vertices. Your exit criteria seem like exit when all paths have been found from point A to B.
Searching has different optimization parameters and the one you cared for is finding a path. You can also be timed constrained or memory constrained, which is what happens in the real world. Not so much that you need all paths. You might have to use other methods such as beam search to get an optimal answer.
This tutorial has different methods to search along a graph: https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-034-artificial-intelligence-fall-2010/tutorials/MIT6_034F10_tutor01.pdf
You might find it useful to implement these other methods.
|
On June 07 2018 00:42 travis wrote:yeah, paths of equal length. in graphs with like, float weights or big weights with huge variance, it probably won't happen. but for graphs with simple weights it happens often, and most unweighted graphs have multiple shortest paths (sometimes an exponential amount of them). I am not sure about the application! That's why I am asking . I suppose it could be useful for routing algorithms to find alternate shortest paths in case a user doesn't like the current suggestion. I also think it has applications in other algorithms that are trying to solve more complicated problems.
Well, one real-world example is the routefinder apps (Google Maps, Waze) that don't give you just 1 route, but one "best" (usually the shortest path in time), but a selection of N (usually 3) routes that are sufficiently different to give you a feeling of choice. However, these are usually just the single shortest path according to some other criterium (shortest distance, cheapest, safest, most scenic, etc.).
Moreover, I suspect for mass applications like Google Maps, TomTom or Waze, they don't compute routes on the fly at all, and instead store trajectories in a table, and have a clever way of matching your route to a trajectory, and then personalize it (Waze, furthermore, appears to add random exploration from time to time). These trajectories must be updated with accurate traffic information, so maybe that is a possible application for finding *all* shortest paths between *all* nodes.
A more classic one is to compute routing tables for network traffic. However these are generally treated as more static. I don't know what the big movers and shakers in routing are doing, but I remember back when I learned about it, they routed most stuff statically, and dynamic routing was used as a fallback. Maybe things changed (are changing? will change?) with IPv6, but I really don't know.
|
![[image loading]](http://asset-8.soupcdn.com/asset/14386/4122_8187_500.jpeg)
Dem news...
|
On June 07 2018 22:47 Manit0u wrote:Dem news...
Amazingly enough all 3 of those are wrong in some aspect or another. I guess the first one is ok as an eli5, but the last two are just plain misleading.
|
On June 07 2018 23:04 Excludos wrote:Amazingly enough all 3 of those are wrong in some aspect or another. I guess the first one is ok as an eli5, but the last two are just plain misleading.
Are you sure the first one is wrong? You might be thinking of a "repository", but this here is a "reposotory"
|
On June 08 2018 02:33 spinesheath wrote:Show nested quote +On June 07 2018 23:04 Excludos wrote:On June 07 2018 22:47 Manit0u wrote:Dem news... Amazingly enough all 3 of those are wrong in some aspect or another. I guess the first one is ok as an eli5, but the last two are just plain misleading. Are you sure the first one is wrong? You might be thinking of a "repository", but this here is a "reposotory"
Omg I didn't even catch that *facepalm*
|
|
|
Related:
![[image loading]](http://asset-2.soupcdn.com/asset/14386/8878_27ae_500.jpeg)
|
So, next week I'll be in Berlin for 5 days. If any of you work/live there and would like to meet for a beer or something just PM me 
I've never been to Berlin before and I hope that my company will book me a hotel in some reasonable location.
|
On June 08 2018 23:40 Manit0u wrote:Related:
Wait, this must be a fake right?
|
On June 12 2018 03:24 sabas123 wrote:Wait, this must be a fake right?
Of course it's fake. It's part of all the memes that came out after GitHub was supposedly being sold to Microsoft.
They're really great.
![[image loading]](http://asset-0.soupcdn.com/asset/14389/2313_004f_500.png)
|
lmfao, ugh so true
windows is soooo ridiculous
a while back I signed up to the windows update program where you get the latest versions of windows 10 ahead of time (i forget what it is called)
I did it because it includes a fully functional ubuntu terminal which is really awesome, though you have to do updates constantly
anyways I can't even tell you how many times I have had a program running overnight (like searching for a TSP solution or something) that was ruined by my computer restarting to install an update. And that's despite the fact that I actually do stay on top of the update scheduling...
|
I've had Windows restart for updates in the middle of comp matches. I understand your pain. This GitHub purchase is definitely not something I'm happy about. I've already cancelled my payments and moved to GitLab which actually is really really good.
|
On June 12 2018 06:09 ShoCkeyy wrote:
I've had Windows restart for updates in the middle of comp matches. I understand your pain. This GitHub purchase is definitely not something I'm happy about. I've already cancelled my payments and moved to GitLab which actually is really really good.
I don't see why. I expect them to change nothing about github. Microsoft have been openly supporting open source for a while now. There's even talks about making windows opensource, which would be mind blowing. All these funny comics are just parodies. I don't for a second expect any of them to come true.
Windows does have a lot of bullshit, but don't just automatically presume that is going to happen to github.
|
I do expect things about github to change, even if it's not noticable. Microsoft is shady as shit. Well, pure evil actually.
I anticipate they will data mine to extremes never before seen. At minimum they will use the repositories to improve various AIs, likely including AIs that code other programs or evolve their own code. But really, I anticipate they will freely steal code(err, umm, "ideas") from private repositories if they find something useful.
But for clarity, please note that I use "microsoft" interchangeably with the DoD/CIA.
|
![[image loading]](https://i.imgur.com/53CbPRU.jpg)
The memes were indeed great.
But I don't think Microsoft is evil or shady as shit. At least, not more evil or shady than Facebook or Google or Apple, or for that matter any other multinational corporation. And just as I trust Google to not poke around in whatever I dump in my Google Drive, I'd trust Microsoft with my code on github. I don't really see why they'd change anything about github except maybe the business model and monetization schemes, which are one of the main reasons Github was looking to sell in the first place: their business model wasn't working. And while I don't understand why Github was worth 7.5BILLION, I don't think Microsoft bought it so that they can rifle through other people's (private) code.
|
|
|
|
|
|
EPT
