Tôi có thể lấy Java thực thi thuật toán Dijkstra ở đâu?

Question

Tôi đang tìm một thực thi Java chung của thuật toán Dijkstra. Tôi đã cố gắng mã hóa điều này một mình, nhưng tôi tiếp tục gặp vấn đề. Nếu nó giúp, tôi biết thực tế là đồ thị luôn được kết nối. Có ai biết về việc thực hiện như vậy không?

Cảm ơn!

Answer 1

Điều này hoàn toàn không biết xấu hổ, nhưng tôi đã mã hóa việc triển khai thuật toán Dijkstra bằng cách sử dụng Fibonacci heaps trong khi quay lại và đăng nó lên trang web cá nhân của tôi. Bạn có thể tìm mã ở đây:

• Dijkstra's algorithm
• Fibonacci heap

Tôi đã cố gắng để bình luận mã để chỉ ra cách thức hoạt động thuật toán, những gì giả định nó làm, vv, do đó hy vọng nó dễ đọc và dễ hiểu. Hãy cho tôi biết nếu có bất cứ điều gì về nó, tôi có thể làm rõ cho bạn.

Hy vọng điều này sẽ hữu ích!

Answer 2

gì bạn có nghĩa này:

(thi JAVA có thể được tìm thấy tại liên kết đề cập (xem dưới cùng của câu trả lời này)

// initialize d to infinity, π and Q to empty 
d = (∞) 
π =() 
S = Q =() 

add s to Q 
d(s) = 0 

while Q is not empty 
{ 
    u = extract-minimum(Q) 
    add u to S 
    relax-neighbors(u) 
} 

relax-neighbors(u) 
{ 
    for each vertex v adjacent to u, v not in S 
    { 
      if d(v) > d(u) + [u,v] // a shorter distance exists 
      { 
       d(v) = d(u) + [u,v] 
       π(v) = u 
       add v to Q 
      } 
    } 
} 

extract-minimum(Q) 
{ 
    find the smallest (as defined by d) vertex in Q 
    remove it from Q and return it 
} 

chỉnh sửa: nhận này từ http://renaud.waldura.com/doc/java/dijkstra/

Answer 3

JGrapht là một thư viện Java phổ biến cho các đồ thị, thuật toán của dijkstra cũng được thực hiện quá

Answer 4

Tài nguyên tốt từ các trường đại học

• Từ Đại học New York tại http://www.cs.nyu.edu/~vs667/development/~DijkstraAlgorithm/

• Từ Đại học Princton tại http://algs4.cs.princeton.edu/41undirected/Graph.java.html

---

Cũng vogella đã thực hiện tốt đẹp tại http://www.vogella.com/articles/JavaAlgorithmsDijkstra/article.html