I am considering a route planning problem, which I try to model with a graph.
I understand that
1. to find a shortest path in a graph, we need to know the weights on the edges.
2. as some places are more desirable to visit than others, we can also have some kind of 'weight' on the nodes. In the case that we want to find a path that maximize the sum of the weights of the nodes passed through, we can convert the original graph to a new one and solve the problem as a shortest path problem in that graph.
I want a way to incorporate both the distance b/w bus stops and the desirability of the bus stops in my consideration of choosing the path.
- Is there way a sensible way to still model this situation by using a graph?
- How can we define the vertices and the edges of this new graph?
- What would be the weight function on the edges?
edit: Not sure why this gets downvoted. Is the question meaningless or a well-known exercise?
Best Answer
I am not sure if there is a way to assign weights to nodes. Perhaps you can replace each node by an edge with negative weight according to its desirability. Also you can have positive weights on the rest of the edges as usual. Now the problem reduces to the known problem of finding shortest path (least total weight). Algorithms such as Dijkstra or Floyd–Warshall algorithm can solve this efficiently. https://en.wikipedia.org/wiki/Shortest_path_problem