GraphAlgorithms

Search This Blog

About

Get link
Facebook
Twitter
Pinterest
Email
Other Apps

This is the Home Assignment for Group 9 S.Y CS-A.

Authors:

Aniruddha Bargaje

Deven Bhadane

Shubham Bodake

Ranjana Burange

Rutika Deshmukh

Get link
Facebook
Twitter
Pinterest
Email
Other Apps

Comments

Shortest Path

Figure shows an animation where the shortest path is determined from vertex 1 to vertex 6 in a graph. The shortest path from one vertex to another vertex is a path in the graph such that the sum of the weights of the edges that should be travelled is minimum. The shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized. The problem of finding the shortest path between two intersections on a road map may be modeled as a special case of the shortest path problem in graphs, where the vertices correspond to intersections and the edges correspond to road segments, each weighted by the length of the segment. Algorithms 1. Dijkstra’s shortest path algorithm Pseudocode Dijkstra’s shortest path algorithm: Algorithm: Mark all nodes unvisited. Create a set of all the unvisited nodes called the unvisited set . Assign to every node a tentative distance value: set it t

Powered by Blogger

About

Comments

Post a Comment