Hvad er vægtede og rettede grafer, og hvilke problemer modellerer de?

Question

IT Interview Practice · Accepted Answer

I en **rettet** graf (digraph) har kanter en **retning** (`A → B` ≠ `B → A`). I en **vægtet** graf bærer hver kant en **numerisk omkostning** (afstand, tid, kapacitet). Kombinationen af begge modellerer reelle systemer, hvor relationer er envejede og har en omkostning.

## Repræsentation

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

## Hvad de modellerer

| Domæne | Knuder | Vægtede rettede kanter |
|---|---|---|
| Kort / GPS | krydsninger | envejsveje + rejsetid |
| Netværk | routere | links + latens/båndbredde |
| Opgaveplanlægning | opgaver | afhængigheder + varigheder |
| Finans | valutaer | vekselkurser |

## Nøglealgoritmier

| Mål | Algoritme | Kompleksitet |
|---|---|---|
| Korteste sti (ikke-negative vægte) | Dijkstra | O((V+E) log V) |
| Korteste sti (negative kanter) | Bellman-Ford | O(VE) |
| Ordning med afhængigheder | Topological sort | O(V+E) |
| Detektion af cyklusser / tilgængelighed | DFS | O(V+E) |

## Hvorfor det betyder noget

Retning og vægt er det, der omdanner en abstrakt graf til en troværdig model for routing-, planlægnings- og afhængighedsproblemer, der driver virkelige applikationer.

Valget af algoritme afhænger af disse egenskaber — for eksempel udelukker negative vægte Dijkstra og kræver Bellman-Ford.

Domæne	Knuder	Vægtede rettede kanter
Kort / GPS	krydsninger	envejsveje + rejsetid
Netværk	routere	links + latens/båndbredde
Opgaveplanlægning	opgaver	afhængigheder + varigheder
Finans	valutaer	vekselkurser

Mål	Algoritme	Kompleksitet
Korteste sti (ikke-negative vægte)	Dijkstra	O((V+E) log V)
Korteste sti (negative kanter)	Bellman-Ford	O(VE)
Ordning med afhængigheder	Topological sort	O(V+E)
Detektion af cyklusser / tilgængelighed	DFS	O(V+E)

Repræsentation

Hvad de modellerer

Nøglealgoritmier

Hvorfor det betyder noget

Relaterede spørgsmål