Vertex vs Edge weights

Vertex weights can be converted to edge weights quite simply:

  • Each vertex $v$ is split into $v_{in}$ and $v_{out}$
  • We put an edge from $v_{in}$ to $v_{out}$ with the weight of the original vertex
  • All edges to $v$ go to $v_{in}$ (their weight is 0)
  • All edges from $v$ go from $v_{out}$ (their weight is 0)
flowchart LR
    2 --> 1
    2 --> 5
    3 --> 7
    5 --> 3
    5 --> 7
    7 --> 2

flowchart LR
    b -->|1| a[ ]
    c -->|0| b[ ]
    c --> |0| d[ ]
    d -->|5| e[ ]
    e -->|0| f[ ]
    e -->|0| h[ ]
    f -->|3| g[ ]
    g -->|0| h[ ]
    h -->|7| i[ ]
    i -->|0| j[ ]
    j -->|2| c[ ]

    style b fill:#f9f,stroke:#333
    style d fill:#f9f,stroke:#333
    style d fill:#f9f,stroke:#333
    style f fill:#f9f,stroke:#333
    style h fill:#f9f,stroke:#333
    style j fill:#f9f,stroke:#333