methodological_instructions (18)

Methodological Instructions

Theme: Algorithms on graphs 

Aim: Implementation of search algorithms on graphs to solve the practical tasks

Lesson objective: Complete program for finding the shortest path using Dijkstra algorithm

Assessment criteria

Knowledge

·     Know what the adjacency matrix is

Comprehension

·     Describe the shortest path algorithm

Application

·     Complete program for finding the shortest path using Dijkstra algorithm

Language objectives

Learners able to …

• State what is the shortest path in graph representation

• Describe the search process in shortest path algorithm

Vocabulary and terminology specific to the subject:

Adjacency matrix, adjacency list,  initial node, path, root, vertices, edge, weighted graph, shortest path

Useful expressions for dialogs and letters:

Well, the Dijkstra algorithm is used when… .

For example, in C# there is Main  …. .

Obviously, finding the shortest path between initial node and ….

Theory

Shortest Path In Graph – Dijkstra’s Algorithm

Dijkstra’s algorithm is an algorithm for finding the shortest paths between nodes in a graph.It was conceived by computer scientist Edsger W. Dijkstra in 1956.This algorithm helps to find the shortest path from a point in a graph (the source) to a destination.

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Diagnostics;

namespace DijkstraAlgorithm

{

    class Dijkstra

    {

        private static int MinimumDistance(int[] distance, bool[] shortestPathTreeSet, int verticesCount)

        {

            int min = int.MaxValue;

            int minIndex = 0;

            for (int v = 0; v < verticesCount; ++v)

            {

                if (shortestPathTreeSet[v] == false && distance[v] <= min)

                {

                    min = distance[v];

                    minIndex = v;

                }

            }

            return minIndex;

        }

        private static void Print(int[] distance, int verticesCount)

        {

            Console.WriteLine("Vertex    Distance from source");

            for (int i = 0; i < verticesCount; ++i)

                Console.WriteLine("{0}\t  {1}", i, distance[i]);

        }

        public static void DijkstraAlgo(int[,] graph, int source, int verticesCount)

        {

            int[] distance = new int[verticesCount];

            bool[] shortestPathTreeSet = new bool[verticesCount];

            for (int i = 0; i < verticesCount; ++i)

            {

                distance[i] = int.MaxValue;

                shortestPathTreeSet[i] = false;

            }

            distance[source] = 0;

            for (int count = 0; count < verticesCount - 1; ++count)

            {

                int u = MinimumDistance(distance, shortestPathTreeSet, verticesCount);

                shortestPathTreeSet[u] = true;

                for (int v = 0; v < verticesCount; ++v)

                    if (!shortestPathTreeSet[v] && Convert.ToBoolean(graph[u, v]) && distance[u] != int.MaxValue && distance[u] + graph[u, v] < distance[v])

                        distance[v] = distance[u] + graph[u, v];

            }

            Print(distance, verticesCount);

        }

        static void Main(string[] args)

        {

            int[,] graph =  {

                         { 0, 6, 0, 0, 0, 0, 0, 9, 0 },

                         { 6, 0, 9, 0, 0, 0, 0, 11, 0 },

                         { 0, 9, 0, 5, 0, 6, 0, 0, 2 },

                         { 0, 0, 5, 0, 9, 16, 0, 0, 0 },

                         { 0, 0, 0, 9, 0, 10, 0, 0, 0 },

                         { 0, 0, 6, 0, 10, 0, 2, 0, 0 },

                         { 0, 0, 0, 16, 0, 2, 0, 1, 6 },

                         { 9, 11, 0, 0, 0, 0, 1, 0, 5 },

                         { 0, 0, 2, 0, 0, 0, 6, 5, 0 }

                            };

            DijkstraAlgo(graph, 0, 9);

        }

    }

}

Output:

Vertex Distance from source
0  0
1  6
2  15
3  20
4  22
5  12
6  10
7  9
8  14
Press any key to continue…

П. Questions for self-assessment.

What is the graph?

What are the benefits of graph representation of data?

Give example of graph use

How to search in binary search tree?

How to find the shortest path to the center of city from your living place?

Visual Aids and Materials links.

1. Slides

2.      https://www.videlin.eu/2016/04/28/shortest-path-in-graph-dijkstras-algorithm-c-implementation/

3.      https://www.csharpstar.com/dijkstra-algorithm-csharp/

4.      https://www.geeksforgeeks.org/csharp-program-for-dijkstras-shortest-path-algorithm-greedy-algo-7/

5.      https://en.wikipedia.org/wiki/Adjacency_matrix

6.      https://www.thecrazyprogrammer.com/2014/03/representation-of-graphs-adjacency-matrix-and-adjacency-list.html

Students' Practical Activities:

Students must be able:

·     Complete program for finding the shortest path using Dijkstra algorithm

Скачано с www.znanio.ru