cuốn sách gpt4 ai đã làm

Thuật toán tốt để tìm đường kính của đồ thị (thưa thớt)?

In lại Tác giả: Taklimakan Thời gian cập nhật: 2023-11-03 02:12:46 26 4
mua khóa gpt4 Nike

Tôi có một biểu đồ lớn, được kết nối, thưa thớt ở dạng danh sách kề. Tôi muốn tìm hai đỉnh càng xa nhau càng tốt, tức là đường kính của đồ thịvà hai đỉnh làm cho điều đó có thể xảy ra.

Tôi quan tâm đến vấn đề này trong cả trường hợp vô hướng và có hướng, cho các ứng dụng khác nhau. Trong trường hợp có hướng, tất nhiên tôi quan tâm đến khoảng cách có hướng (đường đi có hướng ngắn nhất từ ​​đỉnh này sang đỉnh khác).

Có cách nào tốt hơn việc tính toán tất cả các cặp đường đi ngắn nhất không?

biên tập: Tất nhiên, ý tôi muốn nói là "càng xa càng tốt" là "đường đi ngắn nhất dài nhất" - tức là tối đa của tất cả các cặp đỉnh có khoảng cách ngắn nhất từ ​​điểm này đến điểm khác.

câu trả lời hay nhất

Chà, tôi đã suy nghĩ về câu hỏi này và tìm kiếm trên Google, và tôi xin lỗi, nhưng tôi không thể tìm thấy bất kỳ thuật toán nào dường như không "chỉ tìm tất cả các cặp đường đi ngắn nhất".

Nhưng nếu bạn cho rằng Floyd-Warshall là thuật toán duy nhất để tính toán những thứ như vậy (Big-Theta cho |V|^3), thì tôi có một số tin tốt cho bạn: Thuật toán đồ thị thưa thớt của Johnson (cảm ơn bạn, Trusty CLRS!) tính toán tất cả các cặp đường đi ngắn nhất trong (Big-Oh (|V|^2 * lgV + VE)), sẽ nhanh hơn về mặt tiệm cận đối với các đồ thị thưa thớt.

Wikipedia nói rằng nó hoạt động với định hướng (không chắc chắn về vô hướng, nhưng ít nhất tôi không thể nghĩ ra lý do để không), đây là liên kết .

Có điều gì khác về biểu đồ có thể hữu ích không? Nếu nó có thể dễ dàng được ánh xạ lên mặt phẳng 2D (do đó, trọng lượng mặt phẳng và cạnh của nó tuân theo bất đẳng thức tam giác [nó có thể cần phải đáp ứng các yêu cầu nghiêm ngặt hơn, tôi không chắc chắn]), bạn có thể phá vỡ một số thuật toán hình học (thân lồi có thể trong nlogn, từ đó dễ dàng tìm được cặp điểm xa nhất).

Hy vọng điều này sẽ giúp - Agor

EDIT: Hy vọng liên kết hoạt động ngay bây giờ. Nếu không, chỉ cần Google nó. :)

Giới thiệu về thuật toán - Thuật toán tốt để tìm đường kính của đồ thị (thưa thớt)? , chúng tôi đã tìm thấy một câu hỏi tương tự trên Stack Overflow: https://stackoverflow.com/questions/1190543/

26 4 0
Chứng chỉ ICP Bắc Kinh số 000000
Hợp tác quảng cáo: 1813099741@qq.com 6ren.com
Xem sitemap của VNExpress