ក្បួនដោះស្រាយ Bellman-Ford

ក្បួនដោះស្រាយដែលគណនាផ្លូវខ្លីបំផុតពីកំពូលប្រភពមួយទៅកំពូលផ្សេងទៀតទាំងអស់ក្នុងក្រាហ្វទម្ងន់មានទិសដៅ សូម្បីតែជាមួយទម្ងន់គែមអវិជ្ជមាន។

Visualization

Step 1 / 8

Speed:

Details

Analogy

ស្រមៃទីផ្សារប្តូររូបិយប័ណ្ណដែលមានអត្រាប្តូរផ្សេងៗគ្នា។ 'អត្រា' មួយចំនួន (គែម) អាចមានប្រយោជន៍ (ទម្ងន់អវិជ្ជមាន) ដោយសារឱកាសអាប៊ីត្រាហ្ស។ អ្នកចង់រកវិធី 'ថោកបំផុត' ក្នុងការប្តូររូបិយប័ណ្ណរបស់អ្នកទៅជារូបិយប័ណ្ណផ្សេងទៀតទាំងអស់។ Bellman-Ford ដូចជាការធ្វើដដែលៗតាមរយៈការជួញដូរអាចធ្វើបានទាំងអស់ច្រើនដង។ រាល់ពេល អ្នកមើលថាតើការជួញដូរថ្មីអាចផ្តល់ឱ្យអ្នកនូវកិច្ចព្រមព្រៀងដែលប្រសើរជាងសម្រាប់រូបិយប័ណ្ណណាមួយ។ បន្ទាប់ពីវដ្តគ្រប់គ្រាន់ អ្នកនឹងមានអត្រាល្អបំផុត។ ប្រសិនបើតម្លៃនៅតែប្រសើរឡើងគ្មានដែនកំណត់ វាមានន័យថាមានរង្វង់ចំណេញ (វដ្តអវិជ្ជមាន)។

Purpose

ដើម្បីស្វែងរកផ្លូវខ្លីបំផុតពីប្រភពទៅកំពូលផ្សេងទៀតទាំងអស់ក្នុងក្រាហ្វដែលអាចមានទម្ងន់គែមអវិជ្ជមាន។ វាក៏អាចរកឃើញវដ្តទម្ងន់អវិជ្ជមានផងដែរ។

Use Cases

ប្រើក្នុងពិធីការកំណត់ផ្លូវដែលទម្ងន់គែមអាចតំណាងឱ្យម៉ែត្រផ្សេងៗ និងសម្រាប់រកឃើញឱកាសអាប៊ីត្រាហ្សក្នុងហិរញ្ញវត្ថុ។ វាយឺតជាង Dijkstra's ប៉ុន្តែមានលក្ខណៈពិសេសច្រើនដោយសារសមត្ថភាពរបស់វាក្នុងការដោះស្រាយទម្ងន់អវិជ្ជមាន។

Algorithm Steps

Line 1

initialize distances to infinity, dist[start] = 0

for i = 1 to V-1:

for each edge (u, v) with weight w:

if dist[u] + w < dist[v]:

dist[v] = dist[u] + w

for each edge (u, v) with weight w:

if dist[u] + w < dist[v]:

return 'Negative cycle detected'

return dist

Current

Executed

Pending

Explanation

What's Happening?

Step 1/8

ចាប់ផ្តើមចម្ងាយ: S=0, ផ្សេងទៀត=∞។

Updates with each step • Clickfor full view

Code Implementation

def bellman_ford(graph, start_node):
    distances = {node: float('inf') for node in graph}
    distances[start_node] = 0
    num_vertices = len(graph)

    for _ in range(num_vertices - 1):
        for u, edges in graph.items():
            for v, weight in edges.items():
                if distances[u] != float('inf') and distances[u] + weight < distances[v]:
                    distances[v] = distances[u] + weight

    # Check for negative weight cycles
    for u, edges in graph.items():
        for v, weight in edges.items():
            if distances[u] != float('inf') and distances[u] + weight < distances[v]:
                return "Graph contains a negative weight cycle"
                
    return distances