Katika grafu iliyoelekeza (digraph), kingo zina mwelekeo (A → B ≠ B → A). Katika grafu yenye uzani, kila kingo ina (umbali, muda, uwezo). Kuchanganya zote mbili kunaonyesha mifumo ya kweli ambapo mahusiano yana mwelekeo mmoja na una bei.
Katika grafu iliyoelekeza (digraph), kingo zina mwelekeo (A → B ≠ B → A). Katika grafu yenye uzani, kila kingo ina (umbali, muda, uwezo). Kuchanganya zote mbili kunaonyesha mifumo ya kweli ambapo mahusiano yana mwelekeo mmoja na una bei.
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.
| Eneo | Nodi | Kingo zenye uzani na mwelekeo |
|---|---|---|
| Ramani / GPS | njia za mkutano | barabara zenye mwelekeo mmoja + muda wa usafiri |
| Mitandao | ruta | viunganishi + kuchelewa/upana wa bendi |
| Kupanga kazi | kazi | utegemezi + muda |
| Lengo | Algoriti | Matatizo |
|---|---|---|
| Njia fupi (uzani usio hasi) | Dijkstra | O((V+E) log V) |
| Njia fupi (kingo hasi) | Bellman-Ford | O(VE) |
| Kupanga na utegemezi | Kupanga kwa topolojia | O(V+E) |
| Kugundua mizunguko / kufikia | DFS | O(V+E) |
Mwelekeo na uzani ndiyo kinachobadilisha grafu ya kufikiria kuwa mfano wa kutegemeka wa shida za njia, kupanga, na utegemezi ambayo inayoendesha programu za kweli.
Chaguo la algoriti linategemea mali hizi — kwa mfano, uzani hasi hauwezi kutumia Dijkstra na inahitaji Bellman-Ford.
Maktaba ya maswali ya mahojiano ya IT yenye majibu ya kina — kutoka Junior hadi Senior.
Changia