Implementation (Part 2)

Lesson 6 of 9 in Coddy's Dijkstra's Algorithm - Graph Algorithms course.

Now the greedy shortest-path computation.

Challenge

Medium

Now build the full algorithm.

Write a function named dijkstra that takes n, the flat edges array (triples, directed, non-negative weights), and a source, and returns an array where position v is the shortest distance from source to v. Use -1 for vertices that cannot be reached.

Start all distances at a large "infinity" except the source at 0. Then, n times, finalize the closest unvisited vertex and relax its outgoing edges.

Try it yourself

#include <stdlib.h>

int* dijkstra(int n, int* edges, int edges_size, int source, int* returnSize) {
    // Write code here
    *returnSize = 0;
    return edges;
}

Test yourself

This lesson includes a short quiz. Start the lesson to answer it and track your progress.

All lessons in Dijkstra's Algorithm - Graph Algorithms

1Introduction

Introduction Motivation

2The Algorithm

How it works?Pseudo Code Implementation (Part 1)Implementation (Part 2) Project lesson

Time and Space Complexity

3Final Challenges

Final Challenge #1 Final Challenge #2