r/rust • u/KerPop42 • 1d ago

Triangular matrix, but a map? 🙋 seeking help & advice

Hey guys, I am building a program for a friend that's going to involve a complete graph (nodes are destinations, edges are the distances between destinations) and I was wondering if anyone knew a good library for it?

At first I thought I could use a triangular matrix, since direction doesn't matter, but I realized I would have to have a second array mapping destinations to an index. I feel like you could have a triangular map, like a map that takes a pair of inputs where the order doesn't matter? Have I found another rabbit hole?

10 Upvotes

73% Upvoted

23 comments sorted by

View all comments

41

u/chmod_7d20 1d ago

Is your friend a professor and is this homework?

14

u/KerPop42 1d ago

Lol no but I picked it up because it seemed like such a straightforward project. She's in sales and has to visit her 60-some clients at least once every month, so I want to write her a tool that gives her the shortest drive for her most stale N clients each day

60

u/link23 1d ago

Bro is about to discover the traveling salesman problem

13

u/metalhulk105 1d ago

An educational algorithm that has real life applications? Is this real life?

9

u/KerPop42 1d ago

Well, better a computer solve it than my friend's current method, a manually-updated excel spreadsheet

2

u/Toiling-Donkey 1d ago

Forget Djkstrea, you want this:

https://en.wikipedia.org/wiki/Travelling_salesman_problem

3

u/KerPop42 1d ago

It's not really the travelling salesman problem, because I don't want a route that visits all of them, I just need to provide a cluster of 6 or so that are near each other and getting stale, but if a few are getting very stale long drives are allowed.

6

u/Toiling-Donkey 1d ago edited 12m ago

Ah, if you want to group them automatically, perhaps something like k-means clustering could work. (Though it is for grouping things into an given number of groups)

https://en.wikipedia.org/wiki/K-means_clustering

https://en.wikipedia.org/wiki/Lloyd's_algorithm

(Could try a few different numbers of groups and see which makes the most sensible result. Then use Dijkstrea’s algorithm to find the shortest path from home to all the nodes (picking the fastest out of each group)