Блог пользователя iamdumb

Dijktra's algorithm
Автор iamdumb, 9 лет назад, По-английски

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

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
9 лет назад, # |
← Rev. 2   Проголосовать: нравится -9 Проголосовать: не нравится

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)] !

→ Ответить
»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      → Ответить