Description
Find shortest paths from a single source vertex to all other vertices in a weighted directed graph with nonnegative edge weights. Initialize dist[source]=0, dist[v]=∞ for others; priority queue Q with source. Repeatedly extract minimum u from Q; for each neighbor v, relax edge (u,v): if dist[u]+w(u,v) < dist[v], update dist[v] and add v to Q. Greedy. Time O(V²) naive; O(E+V log V) with Fibonacci heap.
Algorithm Flowchart
graph TD
A1["Weighted graph G\nSource vertex s"]
B1["dist s = 0; dist v = inf\nQ = priority queue with s"]
D1{"Q empty?"}
C1["u = extract-min Q"]
C2["For each neighbor v of u\nrelax u v: update dist v"]
F1["Return dist array\nShortest distances"]
A1 --> B1
B1 --> D1
D1 -->|Yes| F1
D1 -->|No| C1
C1 --> C2
C2 --> D1
classDef red fill:#ff6b6b,color:#fff,stroke:#c0392b
classDef yellow fill:#ffd43b,color:#000,stroke:#f59f00
classDef green fill:#51cf66,color:#fff,stroke:#40c057
classDef lightblue fill:#74c0fc,color:#fff,stroke:#4dabf7
classDef violet fill:#b197fc,color:#fff,stroke:#9775fa
classDef lavender fill:#e6e6fa,color:#333,stroke:#b19cd9
class A1 red
class B1 yellow
class C1,C2 green
class F1 violet
class D1 lavender
Color Scheme (GLMP 6-Color)
Red
Triggers & Inputs
Triggers & Inputs
Yellow
Structures & Objects
Structures & Objects
Green
Processing & Operations
Processing & Operations
Light Blue
Intermediates & States
Intermediates & States
Violet
Products & Outputs
Products & Outputs
Lavender
Decision diamonds
Decision diamonds
Process Statistics
- Nodes: 6
- Edges: 6
- OR gates: 1
- Loops: 1
- AND gates: 0
- Complexity: O(V²) or O(E+V log V)
Keywords
- Dijkstra
- shortest path
- graph algorithm
- priority queue
- NIST DADS
- greedy