main2.goで、ノードのコストが分からない場合でも対応できるように改良したもの。

2024年1月5日

ノード間のコストが与えられているダイクストラ計算を行うノードのそれぞれに数値が設定されていて、ノードが持っている数値より小さい数値のノードとは繋がることができない、というアルゴリズムをGo言語で作成する

main2.goで、ノードのコストが分からない場合でも対応できるように改良したもの。

package main

import (
	"fmt"
	"math"
)

type Node struct {
	Name  string
	Value float64 // 各ノードに設定された数値 (負数の場合、この数値を無視する)
}

type Edge struct {
	From   *Node
	To     *Node
	Weight float64
}

func main() {
	/*
		// ノードとエッジを初期化
		nodeA := &Node{Name: "A", Value: 5}
		nodeB := &Node{Name: "B", Value: 8}
		nodeC := &Node{Name: "C", Value: 6}
		nodeD := &Node{Name: "D", Value: 2}
		nodeE := &Node{Name: "E", Value: 4}
	*/

	// ノードとエッジを初期化
	nodeA := &Node{Name: "A", Value: 3}
	nodeB := &Node{Name: "B", Value: -1} // 負数の場合無視
	nodeC := &Node{Name: "C", Value: -1} // 負数の場合無視
	nodeD := &Node{Name: "D", Value: 2}
	nodeE := &Node{Name: "E", Value: -1} // 負数の場合無視
	nodeF := &Node{Name: "F", Value: -1} // 負数の場合無視
	nodeG := &Node{Name: "G", Value: 1}

	/*
		edges := []Edge{
			{nodeA, nodeB, 2},
			{nodeA, nodeC, 4},
			{nodeB, nodeC, 1},
			{nodeB, nodeD, 7},
			{nodeC, nodeD, 3},
			{nodeC, nodeE, 5},
			{nodeE, nodeD, 2},
		}
	*/

	edges := []Edge{ // A,B,C,D,E,Fの順で双方向をしてい
		{nodeA, nodeB, 1},
		{nodeB, nodeA, 1},

		{nodeB, nodeC, 1},
		{nodeC, nodeB, 1},

		{nodeC, nodeD, 1},
		{nodeD, nodeC, 1},

		{nodeD, nodeE, 1},
		{nodeE, nodeD, 1},

		{nodeE, nodeF, 1},
		{nodeF, nodeE, 1},

		{nodeF, nodeG, 1},
		{nodeG, nodeF, 1},
	}

	startNode := nodeG
	targetNode := nodeA

	// ダイクストラアルゴリズムを実行
	shortestPath, totalWeight := dijkstra(startNode, targetNode, edges)

	if shortestPath == nil {
		fmt.Println("最短経路が見つかりませんでした。")
	} else {
		fmt.Printf("最短経路: %v\n", getNodeNames(shortestPath))
		fmt.Printf("最短経路の総重み: %.2f\n", totalWeight)
	}

	fmt.Println(nodeA.Value)
	fmt.Println(nodeB.Value)
	fmt.Println(nodeC.Value)
	fmt.Println(nodeD.Value)
	fmt.Println(nodeE.Value)
	fmt.Println(nodeF.Value)
	fmt.Println(nodeG.Value)

}

func dijkstra(startNode, targetNode *Node, edges []Edge) ([]*Node, float64) {
	// ノード間の最短距離を格納するマップを初期化
	shortestDistances := make(map[*Node]float64)
	// 各ノードの前のノードを格納するマップを初期化
	predecessors := make(map[*Node]*Node)

	// 最短距離を無限大で初期化し、開始ノードの最短距離を0に設定
	for _, edge := range edges {
		shortestDistances[edge.From] = math.Inf(1)
		shortestDistances[edge.To] = math.Inf(1)
	}
	shortestDistances[startNode] = 0

	// 訪問済みのノードを格納するセットを初期化
	visitedNodes := make(map[*Node]bool)

	// まだ訪問していないノードが残っている間ループ
	for len(visitedNodes) < len(shortestDistances) {
		// 未訪問のノードの中から最短距離のノードを選択
		currentNode := getClosestUnvisitedNode(shortestDistances, visitedNodes)

		// ノードがない場合やターゲットノードに到達した場合は終了
		if currentNode == nil || currentNode == targetNode {
			break
		}

		for _, edge := range edges {
			if edge.From == currentNode {
				if edge.To.Value < 0 { // -1などの負数が入っていたら、更新してしまう
					edge.To.Value = currentNode.Value // 下のif文を通す為の手続(書き換えても大丈夫かな(今のところ大丈夫そうだけど))
				}
				if edge.To.Value >= currentNode.Value { //
					distance := shortestDistances[currentNode] + edge.Weight
					if distance < shortestDistances[edge.To] {
						shortestDistances[edge.To] = distance
						predecessors[edge.To] = currentNode
					}
				}
			}
		}

		// このノードを訪問済みとしてマーク
		visitedNodes[currentNode] = true
	}

	// 最短経路を復元
	shortestPath := make([]*Node, 0)
	currentNode := targetNode
	for currentNode != nil {
		shortestPath = append([]*Node{currentNode}, shortestPath...)
		currentNode = predecessors[currentNode]
	}

	// 最短経路の総重みを計算
	totalWeight := shortestDistances[targetNode]

	return shortestPath, totalWeight
}

func getClosestUnvisitedNode(distances map[*Node]float64, visitedNodes map[*Node]bool) *Node {
	minDistance := math.Inf(1)
	var closestNode *Node

	for node, distance := range distances {
		if !visitedNodes[node] && distance < minDistance {
			minDistance = distance
			closestNode = node
		}
	}

	return closestNode
}

func getNodeNames(nodes []*Node) []string {
	names := make([]string, len(nodes))
	for i, node := range nodes {
		names[i] = node.Name
	}
	return names
}

2024年1月5日未分類

Posted by ebata