ਨਿਰਦੇਸ਼ਿਤ ਗ੍ਰਾਫ (digraph) ਵਿੱਚ, ਕਿਨਾਰਿਆਂ ਦੀ ਦਿਸ਼ਾ ਹੁੰਦੀ ਹੈ (A → B ≠ B → A)। ਭਾਰੀ ਗ੍ਰਾਫ ਵਿੱਚ, ਹਰੇਕ ਕਿਨਾਰਾ ਇੱਕ ਸੰਖਿਆਤਮਕ ਲਾਗਤ ਰੱਖਦਾ ਹੈ (ਦੂਰੀ, ਸਮਾਂ, ਸਮਰੱਥਾ)। ਦੋਵਾਂ ਨੂੰ ਮਿਲਾ ਕੇ ਵਾਸਤਵਿਕ ਸਿਸਟਮਾਂ ਦਾ ਮਾਡਲ ਬਣਾਇਆ ਜਾਂਦਾ ਹੈ ਜਿੱਥੇ ਸੰਬੰਧ ਇਕ-ਤਰਫਾ ਅਤੇ ਲਾਗਤ ਸਹਿਤ ਹਨ।
Weighted directed graph:
A --5--> B
A --2--> C
C --1--> B
Adjacency list with weights:
A: [(B,5), (C,2)]
B: []
C: [(B,1)]
graph = {
'A': [('B', 5), ('C', 2)], # directed, weighted edges
'B': [],
'C': [('B', 1)],
}
# Shortest A->B is A->C->B = 2 + 1 = 3, not the direct edge 5.
| ਖੇਤਰ | ਸਿਖਰ | ਭਾਰੀ ਨਿਰਦੇਸ਼ਿਤ ਕਿਨਾਰੇ |
|---|---|---|
| ਨਕਸ਼ੇ / GPS | ਚੌਰਾਹੇ | ਇਕ-ਪਾਸੜ ਸੜਕਾਂ + ਯਾਤਰਾ ਸਮਾਂ |
| ਨੈੱਟਵਰਕ | ਰਾਊਟਰਸ | ਲਿੰਕਸ + ਲੇਟੈਂਸੀ/ਬੈਂਡਵਿਡਥ |
| ਕਾਰਜ ਸ਼ਿਡਿਊਲਿੰਗ | ਕਾਰਜ | ਨਿਰਭਰਤਾਵਾਂ + ਮਿਆਦਾਂ |
| ਵਿੱਤ | ਮੁਦਰਾਵਾਂ | ਵਿਨਿਮੇ ਦਰਾਂ |
| ਲਕਸ਼ | ਐਲਗੋਰਿਦਮ | ਗੁੰਝਲਦਾਰ |
|---|---|---|
| ਛੋਟੀ ਪਾਥ (ਗੈਰ-ਨਕਾਰਾਤਮਕ ਭਾਰ) | Dijkstra | O((V+E) log V) |
| ਛੋਟੀ ਪਾਥ (ਨਕਾਰਾਤਮਕ ਕਿਨਾਰੇ) | Bellman-Ford | O(VE) |
| ਨਿਰਭਰਤਾਵਾਂ ਵਾਲੀ ਤ੍ਰਤੀਬ | Topological sort | O(V+E) |
| ਚੱਕਰ ਖੋਜੋ / ਪਹੁੰਚ | DFS | O(V+E) |
ਦਿਸ਼ਾ ਅਤੇ ਭਾਰ ਉਹ ਹਨ ਜੋ ਇੱਕ ਅਮੂਰਤ ਗ੍ਰਾਫ ਨੂੰ ਰਾਊਟਿੰਗ, ਸ਼ਿਡਿਊਲਿੰਗ, ਅਤੇ ਨਿਰਭਰਤਾ ਸਮੱਸਿਆਵਾਂ ਦੇ ਵਿਸ਼ਵਾਸੂ ਮਾਡਲ ਵਿੱਚ ਬਦਲ ਦਿੰਦੇ ਹਨ ਜੋ ਵਾਸਤਵਿਕ ਐਪਲੀਕੇਸ਼ਨਾਂ ਨੂੰ ਚਲਾਉਂਦੀਆਂ ਹਨ।
ਐਲਗੋਰਿਦਮ ਦੀ ਚੋਣ ਇਹਨਾਂ ਵਿਸ਼ੇਸ਼ਤਾਵਾਂ ਉੱਤੇ ਨਿਰਭਰ ਕਰਦੀ ਹੈ — ਉਦਾਹਰਨ ਲਈ, ਨਕਾਰਾਤਮਕ ਭਾਰ Dijkstra ਨੂੰ ਬਾਹਰ ਕਰਦੇ ਹਨ ਅਤੇ Bellman-Ford ਦੀ ਲੋੜ ਕਰਦੇ ਹਨ।