Dijkstra மற்றும் Bellman-Ford குறுகிய பாதைகளை எவ்வாறு கண்டறிகின்றன?

Question

Accepted Answer

இரண்டும் ஒரு எடையுள்ள வரைபடத்தில் **மூலத்திலிருந்து குறுகிய பாதைகளை** கண்டறிகின்றன. **Dijkstra** வேகமாக உள்ளது ஆனால் **எதிர்மறையற்ற** எடைகள் தேவை; **Bellman-Ford** மெதுவாக உள்ளது ஆனால் **எதிர்மறை** விளிம்புகளை கையாளுகிறது மற்றும் எதிர்மறை சுழற்சிகளை கண்டறிகிறது.

## Dijkstra (பேராசை + min-heap)

பெரும்பாலும் பெரும் அருகிலுள்ள பார்வையிடப்படாத முனையை விரிவுபடுத்தி அதன் அண்டை முனைகளை தளர்த்துகிறது.

```python
import heapq

def dijkstra(graph, src):
    dist = {n: float('inf') for n in graph}
    dist[src] = 0
    pq = [(0, src)]                    # (distance, node)
    while pq:
        d, u = heapq.heappop(pq)       # closest first
        if d > dist[u]:
            continue
        for v, w in graph[u]:
            if d + w < dist[v]:        # relax edge
                dist[v] = d + w
                heapq.heappush(pq, (dist[v], v))
    return dist
```

## Bellman-Ford (DP-போன்ற தளர்த்தல்)

**அனைத்து** விளிம்புகளையும் V-1 முறை தளர்த்துங்கள்; மேலும் தளர்த்தல் ஒரு எதிர்மறை சுழற்சி என்று பொருள்.

## ஒப்பீடு

| | Dijkstra | Bellman-Ford |
|---|---------|--------------||
| எடைகள் | எதிர்மறையற்ற | எந்த (எதிர்மறையுடன் உட்பட) |
| நேரம் | O((V+E) log V) | O(V·E) |
| எதிர்மறை சுழற்சி | n/a | கண்டறிகிறது |

## எப்போது பயன்படுத்த / பக்ஷம்

எதிர்மறையற்ற எடைகளுக்கு **Dijkstra** ஐ இயல்பாக பயன்படுத்தவும் (வரைபடங்கள், நெட்வொர்க்குகள்). எதிர்மறை விளிம்புகள் இருக்கும்போது **Bellman-Ford** ஐ பயன்படுத்தவும் (எ.கா., பாணனம்). Dijkstra எதிர்மறை எடைகளில் அமைதியாக உடைகிறது — ஒரு சிறந்த பதிப்பு.

## ஏன் இது முக்கியமாக உள்ளது

குறுகிய பாதை அல்கோரிதம்கள் ரவுடிங், வழிசெலுத்தல், நெட்வொர்க் நெறிமுறைகள் மற்றும் சார்பு செலவு பகுப்பாய்வை இயக்குகின்றன.

Dijkstra இல் எதிர்மறையற்ற எடை கட்டுப்பாடு பற்றிய அறிவு புலத்தில் தவறான பதிலைத் தடுக்கிறது.

தளர்த்தல் ধারணை பேராசை மற்றும் DP சிந்தனைக்களை இணைக்கிறது, இது ஒரு செழுமையான உயர்-நிலை பொருளாக இருக்கிறது.