• Log InLog In
  • Register
Liquid`
Team Liquid Liquipedia
EST 03:10
CET 09:10
KST 17:10
  • Home
  • Forum
  • Calendar
  • Streams
  • Liquipedia
  • Features
  • Store
  • EPT
  • TL+
  • StarCraft 2
  • Brood War
  • Smash
  • Heroes
  • Counter-Strike
  • Overwatch
  • Liquibet
  • Fantasy StarCraft
  • TLPD
  • StarCraft 2
  • Brood War
  • Blogs
Forum Sidebar
Events/Features
News
Featured News
Team Liquid Map Contest #235[ASL22] Finals Preview: Sweet Victory!12[ASL22] Ro4 Preview: Mirror Mirror6[ASL22] Ro8 Preview: Within Reach5[ASL22] Ro8 Preview: In A Tizzy11
Community News
Weekly Cups (Nov 9-15): Clem and herO take over1Dark completes military service, returns to SC215[BSL23] RO16 Group Stage20Weekly Cups (Nov 2-8): herO back on top?2Weekly Cups (Oct 26 - Nov 1): MaxPax, herO, Solar win0
StarCraft 2
General
Team Liquid Map Contest #23 Dark completes military service, returns to SC2 Weekly Cups (Nov 9-15): Clem and herO take over StarCraft open world shooter announced at BlizzCon No more SC2 streamers on team liquid?
Tourneys
Sparkling Tuna Cup - Weekly Open Tournament RSL goes to London! 2026 Offline Finals Nov 21-22 Sea Duckling Open (Global, Bronze-Diamond) Dark returns! GSL CK #7 4v4 Team Battle (Nov 19) soO & FanTaSy return! SC2 Kevin Scrim 4v4 (Nov 16)
Strategy
[H] ZvP Mid-Late Game: Stalkers Collossi HT
Custom Maps
[G] How to playtest arcade maps Starcraft 2 Advance [D] the control group Simple Questions/Answers
External Content
Mutation # 552 Secret Storm The PondCast: SC2 News & Results Mutation # 551 Robotic Revival Mutation # 550 Graveyard Shift
Brood War
General
List of top players active on ShieldBattery BW General Discussion NaDa's Body Shield Battery Server New Patch BGH Auto Balance -> http://bghmmr.eu/
Tourneys
SC1 Kevin Scrim hosted by SOOP (Nov 18-19) [IPSL] Winter 26-27 Round of 16! [Megathread] Daily Proleagues 2v2v2v2 Tournament Stage 2: Players
Strategy
Pluto's TvP 5Marine 2Medic Push Simple Questions, Simple Answers Infested Terran strategies in 2026 Nuke strategy worked in K-League 2026-11-09
Other Games
General Games
Nintendo Switch Thread Stormgate/Frost Giant Megathread Free Space RTS Game, optimised f. Phone/Tablet etc List of Game Threads The PlayStation 5
Dota 2
League of Legends
[TL LoL EUW IHs] Teemo shall perish
Heroes of the Storm
Heroes of the Storm 2.0
Hearthstone
Deck construction bug
TL Mafia
TL Mafia Community Thread
Community
General
US Politics Mega-thread Trading/Investing Thread Artificial Intelligence Thread Russo-Ukrainian War Thread Things Aren’t Peaceful in Palestine
Fan Clubs
Fan Club Resource Thread Reynor Fan Club The Flash Fan Club
Media & Entertainment
Movie Discussion! Anime Discussion Thread [Manga] One Piece
Sports
Football (Soccer) Thread TeamLiquid Health and Fitness Initiative For 2023
World Cup 2022
Tech Support
Computer Build, Upgrade & Buying Resource Thread
TL Community
The Automated Ban List Recent Gifted Posts
Blogs
The time I organised my…
AssyrianKing
Why I built Repalyzer (1.1.…
BlueStar
Innovate or Game Over?
TrAiDoS
ShieldBattery on Mac
Kraekkling
Can Bots Beat Pros?? Starcr…
namkraft
StarCraft improvement
iopq
Socialism Anyone?
GreenHorizons
Customize Sidebar...

Website Feedback

Closed Threads



Active: 16865 users

The Big Programming Thread - Page 965

Forum Index > General Forum
Post a Reply
Prev 1 963 964 965 966 967 1032 Next
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.
beg
Profile Blog Joined May 2010
991 Posts
Last Edited: 2018-06-06 13:24:59
June 06 2018 13:21 GMT
#19281
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.)
Deleted User 3420
Profile Blog Joined May 2003
24492 Posts
June 06 2018 13:52 GMT
#19282
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?
emperorchampion
Profile Blog Joined December 2008
Canada9496 Posts
Last Edited: 2018-06-06 14:49:15
June 06 2018 14:47 GMT
#19283
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?
TRUEESPORTS || your days as a respected member of team liquid are over
Deleted User 3420
Profile Blog Joined May 2003
24492 Posts
June 06 2018 15:42 GMT
#19284
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.
Neshapotamus
Profile Blog Joined May 2006
United States163 Posts
June 07 2018 02:33 GMT
#19285
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.
Acrofales
Profile Joined August 2010
Spain18502 Posts
Last Edited: 2018-06-07 04:16:57
June 07 2018 04:16 GMT
#19286
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.
Manit0u
Profile Blog Joined August 2004
Poland17875 Posts
June 07 2018 13:47 GMT
#19287
[image loading]

Dem news...
Time is precious. Waste it wisely.
Excludos
Profile Blog Joined April 2010
Norway8281 Posts
June 07 2018 14:04 GMT
#19288
On June 07 2018 22:47 Manit0u wrote:
[image loading]

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.
spinesheath
Profile Blog Joined June 2009
Germany8679 Posts
June 07 2018 17:33 GMT
#19289
On June 07 2018 23:04 Excludos wrote:
Show nested quote +
On June 07 2018 22:47 Manit0u wrote:
[image loading]

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"
If you have a good reason to disagree with the above, please tell me. Thank you.
Excludos
Profile Blog Joined April 2010
Norway8281 Posts
June 07 2018 17:44 GMT
#19290
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:
[image loading]

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*
bo1b
Profile Blog Joined August 2012
Australia12814 Posts
June 07 2018 23:22 GMT
#19291
That is a great picture.
Manit0u
Profile Blog Joined August 2004
Poland17875 Posts
June 08 2018 14:40 GMT
#19292
Related:

[image loading]
Time is precious. Waste it wisely.
Manit0u
Profile Blog Joined August 2004
Poland17875 Posts
June 11 2018 13:45 GMT
#19293
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.
Time is precious. Waste it wisely.
sabas123
Profile Blog Joined December 2010
Netherlands3122 Posts
June 11 2018 18:24 GMT
#19294
On June 08 2018 23:40 Manit0u wrote:
Related:

[image loading]

Wait, this must be a fake right?
The harder it becomes, the more you should focus on the basics.
Manit0u
Profile Blog Joined August 2004
Poland17875 Posts
Last Edited: 2018-06-11 19:06:57
June 11 2018 19:00 GMT
#19295
On June 12 2018 03:24 sabas123 wrote:
Show nested quote +
On June 08 2018 23:40 Manit0u wrote:
Related:

[image loading]

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]
Time is precious. Waste it wisely.
Deleted User 3420
Profile Blog Joined May 2003
24492 Posts
June 11 2018 20:12 GMT
#19296
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...
ShoCkeyy
Profile Blog Joined July 2008
7815 Posts
June 11 2018 21:09 GMT
#19297
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.
Life?
Excludos
Profile Blog Joined April 2010
Norway8281 Posts
Last Edited: 2018-06-11 21:33:33
June 11 2018 21:32 GMT
#19298
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.
Deleted User 3420
Profile Blog Joined May 2003
24492 Posts
Last Edited: 2018-06-11 21:58:43
June 11 2018 21:56 GMT
#19299
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.
Acrofales
Profile Joined August 2010
Spain18502 Posts
June 11 2018 22:24 GMT
#19300
[image loading]

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.
Prev 1 963 964 965 966 967 1032 Next
Please log in or register to reply.
Live Events Refresh
Next event in 1h 51m
[ Submit Event ]
Live Streams
Refresh
StarCraft 2
ProTech144
SortOf 136
StarCraft: Brood War
Calm 3357
Bisu 458
Hyuk 262
ToSsGirL 252
Soulkey 117
actioN 78
Snow 68
Larva 50
ZergMaN 23
Barracks 15
[ Show more ]
JYJ 15
sOs 10
Force[name] 6
Sharp 6
Killer 1
League of Legends
JimRising 687
Super Smash Bros
Mew2King72
Heroes of the Storm
Trikslyr47
Other Games
summit1g13191
WinterStarcraft634
ceh9426
Happy226
ViBE58
Organizations
Other Games
gamesdonequick568
[ Show 10 non-featured ]
StarCraft 2
• AfreecaTV YouTube
• intothetv
• Kozan
• IndyKCrew
• Migwel
StarCraft: Brood War
• BSLYoutube
• STPLYoutube
• ZZZeroYoutube
Dota 2
• lizZardDota2222
League of Legends
• Rush1332
Upcoming Events
The PondCast
1h 51m
University League
1h 51m
LiuLi Cup
2h 51m
Rogue vs TBD
Maru vs TBD
OSC
7h 51m
Replay Cast
14h 51m
GSL
1d 3h
Maru vs Dark
Patches Events
1d 5h
OSC
1d 7h
Replay Cast
1d 14h
KCM Race Survival
2 days
[ Show More ]
Ultimate Battle
2 days
ZerO vs Bisu
RSL Revival
3 days
BSL
3 days
eOnzErG vs StRyKeR
Cross vs JDConan
RSL Revival
4 days
IPSL
4 days
Ret vs ggnore13
nOmaD vs Aether
BSL
4 days
Bonyth vs Doodle
Kyrie vs Jimin
Replay Cast
4 days
WardiTV Weekly
5 days
Kung Fu Cup
6 days
Solar vs Classic
ByuN vs SHIN
PiGosaur Cup
6 days
Liquipedia Results

Completed

Proleague 2026-11-16
Blizzard Classic Cup 2026
HCC Season 3

Ongoing

Acropolis #5
KCM Race Survival 2026 Season 4
International ShieldBattery League
BSL Season 23
IPSL Winter 2026-27
Calamity Cup Div. A Season 8
Underdog Cup 2026 Div 2-3
Stake Ranked Episode 6
BLAST Rivals Fall 2026
IEM Beijing 2026
PGL Masters Bucharest 2026
Stake Ranked Episode 5
1win Private Club #2
Thunderpick World Champ. '26
ESL Pro League Season 24
Stake Ranked Episode 4
1win Private Club #1
Logitech G Play Connect 2026
SL StarSeries Fall 2026
FISSURE Playground #3
BLAST Open Fall 2026

Upcoming

Sector 591
YSL S4
SC4ALL II: Brood War
NBSL 2026 Xiamen LAN
BSL 23: Non-Korean Championship
HSC XXX
Stellar Fest 2: Lunar Cup
StarCraft2 Weekly Open Tournament 2026 Grand Finals
SC4ALL II: StarCraft II
Kung Fu Cup 2026 Grand Finals
RSL Offline Finals
IEM Kraków 2027
PGL Bucharest 2027
BLAST Bounty Winter 2027
PGL Major Singapore 2026
TLPD

1. ByuN
2. TY
3. Dark
4. Solar
5. Stats
6. Nerchio
7. sOs
8. soO
9. INnoVation
10. Elazer
1. Rain
2. Flash
3. EffOrt
4. Last
5. Bisu
6. Soulkey
7. Mini
8. Sharp
Sidebar Settings...

Advertising | Privacy Policy | Terms Of Use | Contact Us

Original banner artwork: Jim Warren
The contents of this webpage are copyright © 2026 TLnet. All Rights Reserved.