Shortest path (Dijkstra)

Challenge

Weighted directed graph as a matrix: w[i*n+j] is a positive edge weight, or 0 for no edge.

int dijkstra_distance(const int *w,int n,int src,int dst);

Return the shortest-path distance src→dst, or −1 if unreachable. src==dst → 0.

Input format

w n×n, weights ≥1 or 0=no edge.

Output format

Shortest distance, or −1.

Constraints

All weights positive (Dijkstra assumption).

Starter code

#include <stddef.h>
/* Weighted directed graph: w[i*n+j] is a positive edge weight, or 0 for no edge. Shortest-path distance src->dst (Dijkstra), or -1 if unreachable. src==dst -> 0. */
int dijkstra_distance(const int *w,int n,int src,int dst){ (void)w;(void)n;(void)src;(void)dst; return -1; }

Common mistakes

Treating weight 0 as a real edge; using BFS (ignores weights).

Edge cases to handle

src==dst → 0; unreachable → −1.

Background lessons

• Dijkstra's shortest path