The table gives the weight of each edge in a weighted graph with vertices a, b,

Question

The table gives the weight of each edge in a weighted graph with vertices a, b, c, d, e, f, and g. Use Dijkstra's algorithm to find the path of least total weight from a to g.

Explanation / Answer

Shortest Path using Dijkstras Algorithm Def:shortest path algorithm Used to find the shortest path between two nodes in a network. ->Dijkstras algorithm finds a shortest path tree from a single source node, by building a set of nodes that have minimum distance from the source. =>It maintains a list of unvisited vertices. =>It chooses a vertex (the source) and assigns a maximum possible cost (i.e. infinity) to every other vertex. =>The cost of the source remains zero as it actually takes nothing to reach from the source vertex to itself. =>In every subsequent step of the algorithm it tries to improve(minimize) the cost for each vertex. Here the cost can be distance,time taken to reach that vertex from the source vertex. The minimization of cost is a multi-step process. =>For each unvisited neighbor (vertex 2, vertex 3, vertex 4) of the current vertex (vertex 1) calculate the new cost from the vertex (vertex 1). For Example, The new cost of vertex 2 is calculated as the minimum of the two (existing cost of vertex 2) When all the neighbors of the current node are considered, it marks the current node as visited and is removed from the unvisited list. Select a vertex from the list of unvisited nodes (which has the smallest cost) and repeat step 4. At the end there will be no possibilities to improve it further and then the algorithm ends Algorithm: function Dijkstra(Graph, source) { dist[source]:= 0 // Distance from source to source is set to 0 for each vertex v in Graph: // Initializations if v =source { dist[v]:=infinity // Unknown distance function from source to each node set to infinity add v to Q } // All nodes initially in Q while (Q!=NULL) Q is not empty: { // The main loop v := vertex in Q with min dist[v] // In the first run-through, this vertex is the source node remove v from Q for each neighbor u of v: // where neighbor u has not yet been removed from Q. arr := dist[v] + length(v, u) if (arr

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.