Better performance for the shortest paths in undirected unweighted graph
up vote
1
down vote
favorite
I got the undirected unweighted graph. Where every node represents one city. Every city produces one type of grocery (does not have to be unique).
Then you will have on the input a number of type groceries which has to be delivered to every city. You can transport every grocery separately and it has to be the shortest way. The distance between every node is 1.
Actually, I'm using BFS for every node. But there should be a better solution.
Example:
INPUT:
5(number of nodes) 5(number of edges)
4(number of groceries) 3(required number of groceries in every city)
0 1 3 2 1 ( city(node number) has grocery 0->0 1->1 2->3 3->2 4->1)
0 1 (edges)
2 1 (edges)
2 3 (edges)
3 0 (edges)
4 3 (edges)
OUTPUT:
11 (total distance)
2(total distance for town) 0 1 2 (groceries in the city)
2 1 0 3
2 3 1 2
2 2 0 1
3 1 2 0
graph-theory shortest-path breadth-first-search
edited Nov 9 at 22:19
Dominique Fortin
1,622816
asked Oct 17 at 19:37
Lukáš Frajt
10619
add a comment |
up vote
1
down vote
favorite
I got the undirected unweighted graph. Where every node represents one city. Every city produces one type of grocery (does not have to be unique).
Then you will have on the input a number of type groceries which has to be delivered to every city. You can transport every grocery separately and it has to be the shortest way. The distance between every node is 1.
Actually, I'm using BFS for every node. But there should be a better solution.
Example:
INPUT:
5(number of nodes) 5(number of edges)
4(number of groceries) 3(required number of groceries in every city)
0 1 3 2 1 ( city(node number) has grocery 0->0 1->1 2->3 3->2 4->1)
0 1 (edges)
2 1 (edges)
2 3 (edges)
3 0 (edges)
4 3 (edges)
OUTPUT:
11 (total distance)
2(total distance for town) 0 1 2 (groceries in the city)
2 1 0 3
2 3 1 2
2 2 0 1
3 1 2 0
graph-theory shortest-path breadth-first-search
edited Nov 9 at 22:19
Dominique Fortin
1,622816
asked Oct 17 at 19:37
Lukáš Frajt
10619
1
You can do one BFS per grocery type, if there are not many.
– zch
Nov 9 at 22:49
add a comment |
up vote
1
down vote
favorite
up vote
1
down vote
favorite
I got the undirected unweighted graph. Where every node represents one city. Every city produces one type of grocery (does not have to be unique).
Then you will have on the input a number of type groceries which has to be delivered to every city. You can transport every grocery separately and it has to be the shortest way. The distance between every node is 1.
Actually, I'm using BFS for every node. But there should be a better solution.
Example:
INPUT:
5(number of nodes) 5(number of edges)
4(number of groceries) 3(required number of groceries in every city)
0 1 3 2 1 ( city(node number) has grocery 0->0 1->1 2->3 3->2 4->1)
0 1 (edges)
2 1 (edges)
2 3 (edges)
3 0 (edges)
4 3 (edges)
OUTPUT:
11 (total distance)
2(total distance for town) 0 1 2 (groceries in the city)
2 1 0 3
2 3 1 2
2 2 0 1
3 1 2 0
graph-theory shortest-path breadth-first-search
edited Nov 9 at 22:19
Dominique Fortin
1,622816
asked Oct 17 at 19:37
Lukáš Frajt
10619
I got the undirected unweighted graph. Where every node represents one city. Every city produces one type of grocery (does not have to be unique).
Then you will have on the input a number of type groceries which has to be delivered to every city. You can transport every grocery separately and it has to be the shortest way. The distance between every node is 1.
Actually, I'm using BFS for every node. But there should be a better solution.
Example:
INPUT:
5(number of nodes) 5(number of edges)
4(number of groceries) 3(required number of groceries in every city)
0 1 3 2 1 ( city(node number) has grocery 0->0 1->1 2->3 3->2 4->1)
0 1 (edges)
2 1 (edges)
2 3 (edges)
3 0 (edges)
4 3 (edges)
OUTPUT:
11 (total distance)
2(total distance for town) 0 1 2 (groceries in the city)
2 1 0 3
2 3 1 2
2 2 0 1
3 1 2 0
graph-theory shortest-path breadth-first-search
graph-theory shortest-path breadth-first-search
edited Nov 9 at 22:19
Dominique Fortin
1,622816
asked Oct 17 at 19:37
Lukáš Frajt
10619
edited Nov 9 at 22:19
Dominique Fortin
1,622816
asked Oct 17 at 19:37
Lukáš Frajt
10619
edited Nov 9 at 22:19
Dominique Fortin
1,622816
edited Nov 9 at 22:19
Dominique Fortin
1,622816
edited Nov 9 at 22:19
Dominique Fortin
1,622816
1,622816
asked Oct 17 at 19:37
Lukáš Frajt
10619
asked Oct 17 at 19:37
Lukáš Frajt
10619
asked Oct 17 at 19:37
Lukáš Frajt
10619
10619
1
You can do one BFS per grocery type, if there are not many.
– zch
Nov 9 at 22:49
add a comment |
1
You can do one BFS per grocery type, if there are not many.
– zch
Nov 9 at 22:49
1
1
You can do one BFS per grocery type, if there are not many.
– zch
Nov 9 at 22:49
You can do one BFS per grocery type, if there are not many.
– zch
Nov 9 at 22:49
add a comment |
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f52862402%2fbetter-performance-for-the-shortest-paths-in-undirected-unweighted-graph%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
You can do one BFS per grocery type, if there are not many.
– zch
Nov 9 at 22:49