Apa yaiku graf berbobot lan graf berarah, lan masalah apa sing dimodelake?

Question

Accepted Answer

Ing graf **berarah** (digraph), pinggir nduweni **arah** (`A → B` ≠ `B → A`). Ing graf **berbobot**, saben pinggir nduwe **biaya numerik** (jarak, wektu, kapasitas). Nggabungake loro-lorone memodelake sistem nyata ing ngendi hubungan melu-melu lan nduweni biaya.

## Representation

```text
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)]
```

```python
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.
```

## What they model

| Domain | Vertices | Weighted directed edges |
|---|---|---|
| Maps / GPS | intersections | one-way roads + travel time |
| Networks | routers | links + latency/bandwidth |
| Task scheduling | tasks | dependencies + durations |
| Finance | currencies | exchange rates |

## Key algorithms

| Goal | Algorithm | Complexity |
|---|---|---|
| Shortest path (non-negative weights) | Dijkstra | O((V+E) log V) |
| Shortest path (negative edges) | Bellman-Ford | O(VE) |
| Ordering with dependencies | Topological sort | O(V+E) |
| Detect cycles / reachability | DFS | O(V+E) |

## Kenapa Penting

Arah lan bobot minangka apa sing ngubahe graf abstrak dadi model setya saka masalah routing, penjadwalan, lan ketergantungan sing nyaur aplikasi nyata.

Pilihan algoritma gumantung ing sifat-sifat iki — contone, bobot negatif ngluarake Dijkstra lan butuh Bellman-Ford.

Domain	Vertices	Weighted directed edges
Maps / GPS	intersections	one-way roads + travel time
Networks	routers	links + latency/bandwidth
Task scheduling	tasks	dependencies + durations
Finance	currencies	exchange rates

Goal	Algorithm	Complexity
Shortest path (non-negative weights)	Dijkstra	O((V+E) log V)
Shortest path (negative edges)	Bellman-Ford	O(VE)
Ordering with dependencies	Topological sort	O(V+E)
Detect cycles / reachability	DFS	O(V+E)