iamdumb's blog

Dijktra's algorithm
By iamdumb, 9 years ago, In English

Hello,i learned Dijkstra's algorithm for finding ShortestPath to all vertices.I learned adjacency Matrix version from this source.I have a little doubt that how to find shortest path when we have our vertices not a single number but a pair of two numbers,more specifically say a coordinate(x,y).How to modify our original dijkstra's to solve this.This question needs above modification

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
9 years ago, # |
← Rev. 2   Vote: I like it -9 Vote: I do not like it

you can use 

#include<map> 
map<pair<int, int>, int> MP;

it make a number for any pair you give it.

like : MP[(1, 2)] = 1; and when you want call that, just type MP[(1, 2)] !

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

As N is so small (<= 1000), you can build up a complete graph of size (N + 2) (That is, a graph of (N + 2) vertices and every pair of vertices has an edge equals to dist(u, v)^2 as described by problem) (Notice that we add starting point and ending point to the vertex list), then you can run Dijkstra in O(V^2) or O(E lg V) = O(V^2 lg V), using maybe different implementations.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    thank u so much,can you tell me where i can learn this thing...i mean in great detail

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Emm by detail you mean more pseudocode or actual codes? btw I suggest you to learn (and write) the linked list version, as if I'm correct adj matrix yields an O(V^2) complexity, if V is larger this is going to be a problem.

      → Reply