4

GA: 7. Dijkstra's algorithm

 2 years ago
source link: https://mingzhi198.github.io/p/ga-7.-dijkstras-algorithm/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

Statement

  • This article is my study notes from the book: grokking algorithm: an illustrated guide for programmers and other curious people.
  • Please refer to the original work for more details and indicate the source for reprinting.
  • Weighted graphs: assigning weight to some edges.
  • Dijkstra’s algorithm: What’s the shortest path to X?
  • Cycles in graphs will make Dijkstra’s algorithm not work.

Dijkstra’s algorithm

Sometimes the shortest path is not the fastest path, since there are different weights with various edges.

short_path.png
fast_path.png

In the figures above, you are going to walk from home to shool.
By using BFS, we will find the shortest path A, while Dijkstra’s algorithm is better for us to find the fastest path.
Therefore, you will choose path B instead of path A, since it will take you less time from home to school.

Four steps of Dijkstra’s algorithm

  • A. Find the node that will take you the least time to get to.
  • B. Update the costs of this node’s neighbors.
  • C. Repeat until you’ve done this for all nodes in the graph.
  • D. Get the final path.
dijkstra_step1.jpg

In the figure above, we want to walk from Begin to the End.
Step A: It will take you 6 minutes from Begin to A and 2 minutes from Begin to B.

Step B: Find how long it will take you to get to B’s neighbors by following edges from B.

  • You find that it will take less time to get to A and 7 minutes to get to End. Then, we update the costs.
    dijkstra_step2.jpg

Step C: Repeat steps above.

Step A: Now, we find that Node A will take you less time to get to.
Step B: Update the costs of neighbors of Node A.

dijkstra_step3.jpg

Finally, we find that it only take us 6 minutes to get to the End.

  • Remember that Dijkstra’s algorithm can only be used in directed acyclic graphs, which is called DAGs.

Trading for a piano

Here, the author provide an example to further illustrate Dijkstra’s algorithm.

trade_graph.jpg

You have a book, and other people have other items, the relationship of which you can see from the figure above.
In the figure, you want trade your book for the piano.
To solve this problem, we should follow the steps of Dijkstra’s algorithm.

  • Step 1: Find the node with the least cost.
    We can see from the figure that it costs you 0 to get to poster, which is our target.
  • Step 2: Find the costs of it’s neighbors
    We compare the costs to it’s neighbors, and update the costs with smaller values and their parents(from which node we get to these neighbors).
trade_poster.jpg
  • Repeat:
  • Step 1: The node LP is the next one with the least cost.
  • Step 2: Update the costs and parent of LP’s neighbors.
trade_lp_neighbors.jpg
  • Repeat:
  • Step 1: The node Guitar is the next one with the least cost.
  • Step 2: Update the costs and parent of Guitar’s neighbors.
trade_guitar_neighbors.jpg
  • Repeat:
  • Step 1: the node Drum is the last one to be processed.
  • Step 2: Update the costs and parent of Drum’s neighbors.
trade_final_path.jpg

Finally, we get the cheapest path: Book->LP->Drum->Piano

Implementation

  • Golang
package main

import (
	"fmt"
	"math"
	"util"
)

type Node struct {
	Name string
	Cost int
}

type Table struct {
	Name   string
	Parent string
	Cost   int
}

var (
	graph map[string][]*Node
	table map[string]*Table
)

func init() {
	graph = make(map[string][]*Node, 6)
	graph["book"] = []*Node{
		&Node{Name: "lp", Cost: 5},
		&Node{Name: "poster", Cost: 0},
	}
	graph["poster"] = []*Node{
		&Node{Name: "guitar", Cost: 30},
		&Node{Name: "drum", Cost: 35},
	}
	graph["lp"] = []*Node{
		&Node{Name: "guitar", Cost: 15},
		&Node{Name: "drum", Cost: 20},
	}
	graph["guitar"] = []*Node{
		&Node{Name: "piano", Cost: 20},
	}
	graph["drum"] = []*Node{
		&Node{Name: "piano", Cost: 10},
	}
	graph["piano"] = []*Node{}

	table = make(map[string]*Table, 5)
	table["lp"] = &Table{Name: "lp", Cost: 5, Parent: "book"}
	table["poster"] = &Table{Name: "poster", Cost: 0, Parent: "book"}
	table["guitar"] = &Table{Name: "guitar", Cost: math.MaxUint32, Parent: ""}
	table["drum"] = &Table{Name: "drum", Cost: math.MaxUint32, Parent: ""}
	table["piano"] = &Table{Name: "piano", Cost: math.MaxUint32, Parent: ""}
	return
}

func GetDijkstraPath(table map[string]*Table, name string) (ret []string) {
	ret = append(ret, name)
	for {
		nodeT, ok := table[name]
		if !ok {
			break
		}
		ret = append(ret, nodeT.Parent)
		name = nodeT.Parent
	}
	n := len(ret)
	for i := 0; i < n/2; i++ {
		ret[i], ret[n-i-1] = ret[n-i-1], ret[i]
	}
	return
}

func FindCheapestNode(list map[string]*Table, lastMinCost int) (min *Table) {
	if len(list) <= 0 {
		return
	}

	for _, tab := range list {
		// Be careful that the minimal value we want must be bigger than the last minimal value.
		// And there will be no cheaper node than the last minimal cost
		if tab.Cost <= lastMinCost {
			continue
		}
		if nil == min {
			min = tab
			continue
		}
		if tab.Cost < min.Cost {
			min = tab
		}
	}
	return
}

func Dijkstra(graph map[string][]*Node, name string) (finalPath []string, totalCost int) {
	lastMinCost := -1
	for i := 0; i < len(table); i++ {
		// 1. find the cheapst node
		node := FindCheapestNode(table, lastMinCost)
		fmt.Println("cheapest node: ", util.ToString(node))
		lastMinCost = node.Cost

		// 2. update it's neighbors' cost and parent
		for _, neighbor := range graph[node.Name] {
			neighborT, ok := table[neighbor.Name]
			if !ok {
				table[neighbor.Name] = &Table{Name: neighbor.Name}
			}
			neighborT.Cost = node.Cost + neighbor.Cost // update cost
			neighborT.Parent = node.Name               // update parent
		}
	}
	fmt.Println(util.ToStringIndent(table))

	finalPath = GetDijkstraPath(table, name)
	totalCost = table[name].Cost
	return
}

func main() {
	path, cost := Dijkstra(graph, "piano")
	fmt.Printf("Dijkstra path: %s, cost: %d\n", path, cost)
}
  • Output
cheapest node:  {"Name":"poster","Parent":"book","Cost":0}
cheapest node:  {"Name":"lp","Parent":"book","Cost":5}
cheapest node:  {"Name":"guitar","Parent":"lp","Cost":20}
cheapest node:  {"Name":"drum","Parent":"lp","Cost":25}
cheapest node:  {"Name":"piano","Parent":"drum","Cost":35}
{
  "drum": {
    "Name": "drum",
    "Parent": "lp",
    "Cost": 25
  },
  "guitar": {
    "Name": "guitar",
    "Parent": "lp",
    "Cost": 20
  },
  "lp": {
    "Name": "lp",
    "Parent": "book",
    "Cost": 5
  },
  "piano": {
    "Name": "piano",
    "Parent": "drum",
    "Cost": 35
  },
  "poster": {
    "Name": "poster",
    "Parent": "book",
    "Cost": 0
  }
}
Dijkstra path: [book lp drum piano], cost: 35

Negative-weight edges

Implementation

Summary


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK