CODEWITHSUNDEEP
algorithmdijkstra
daihovey
daihovey

Reputation: 3575

Dijkstra path weight

Dijkstra

Why would some paths have significantly more / less weights than other equal length paths? In Dijkstra's do length and path weight not equate?

Upvotes: 1

Views: 471

Answers (2)

woliveirajr
woliveirajr

Reputation: 9483

You mean that the graphical representation of the graph doesn't correspond to the weight each path has ?

They don't have too... the visual representation is just a representation, nothing else. It isn't oblied be equivalent of the weight.

You could redraw the graph anyway you like, just making sure that the connections between the vertices are kept.

Edit: and it doesn't matter what kind of graph you're dealing with, be it Dijkstra or any other. You can even fidn graphs where the direction matters: From A to B the weight can be 10 and from B to A the weight can be 30. No problem.

Edit 2: the image just shows how the vertices connect to each other. The image doesn't need to be in scale with the graph that is stored in your program. Sometimes you'll have graphs with so many vertices and edges that you won't be able to represent it in a good way. What matters for your programing problems are the vertices, the edges, and it's weights. The image is just a rough representation of it. You can redraw the image as you like, you just have to make sure to put all vertices, all edges, and all weights for each edge.

Upvotes: 4

Jeff Foster
Jeff Foster

Reputation: 44736

The length of the path (as in the size of the line in the diagram) is irrelevant, it's only to make it look nice. The weight of the line indicates the cost of travelling between two nodes.

It is confusing though, and you could make length = weight by changing the way the graph is drawn.

Upvotes: 2

Related Questions