Everyone is welcome to watch my algorithm design and analysis column: Algorithm Design and Analysis_IT Yan’s Blog-CSDN Blog I hope it will be helpful to everyone!
Personal column:
Algorithm design and analysis: Algorithm design and analysis_IT Yan’s blog-CSDN blog
Java Basics: Java Basics_IT Yan’s Blog-CSDN Blog
C language: c language_IT Yan’s blog-CSDN blog
MySQL: Data Structure_IT Yan’s Blog-CSDN Blog
Data structure: Data structure_IT Yan’s blog-CSDN blog
C++: C++_IT Yan’s Blog-CSDN Blog
C51 MCU: C51 MCU (STC89C516)_IT Yan’s Blog-CSDN Blog
Webpage design and application based on HTML5: Webpage design and application based on HTML5_IT Yan’s Blog-CSDN Blog
python: python_IT Yan’s blog-CSDN blog
Welcome to watch, I hope it is useful to everyone!
Table of Contents
Purpose:
content:
Code (Java):
operation result:
Analysis of Algorithms:
Implementation of other programming languages:
C language program:
python program:
C++ program:
Purpose:
1) Understand the idea and basic principles of greedy algorithm;
2) Master the general characteristics of using greedy algorithms to solve problems;
3) Be able to correctly choose greedy strategies for practical problems;
4) Be able to prove the correctness of the algorithm for the selected greedy strategy;
5) Be able to write code correctly according to the greedy strategy;
6) Be able to correctly analyze the time complexity and space complexity of the algorithm.
content:
Greedy algorithm for single source shortest path.
The test data can be used as shown in the figure below, 1 is the source point:
Code (Java):
package one;
public class Three {
public static void main(String[] args) {
// TODO Auto-generated method stub
int x1[][] = { { 0, 2, 0, 1, 0, 3, 0, 0 }, { 0, 0, 6, 0, 5, 0, 0, 0 }, { 0, 0, 0 , 0, 0, 0, 0, 6 },
{ 0, 10, 0, 0, 0, 0, 2, 0 }, { 0, 0, 9, 0, 0, 0, 0, 4 }, { 0, 0, 0, 5, 0, 0, 4 , 0 },
{ 0, 7, 0, 0, 3, 0, 0, 8 }, { 0, 0, 0, 0, 0, 0, 0, 0 } };
int s = 1;// represents the origin
int[] dist = new int[x1.length];// represents the shortest distance from the origin to each point
boolean[] visited = new boolean[x1.length];
int [] pre=new int[x1.length];//Record the predecessor node of the shortest path
for (int i = 0; i < x1.length; i + + ) {//Initialization
dist[i] = Integer.MAX_VALUE; // Initialized to infinity
visited[i] = false; // Initialized to have not been visited
pre[i]=-1;//Initialize to -1
}
dist[s - 1] = 0;//from itself to itself is 0
// Find the distance from the origin to each vertex
for (int i = 0; i < x1.length; i + + ) {
int mindist = Integer.MAX_VALUE; // shortest path
int mindistindex = -1; // Index of the shortest path
// Find the shortest path
for (int j = 0; j < x1.length; j + + ) {
if (!(visited[j]) & amp; & amp; dist[j] < mindist) {
\t\t\t\t\t// update data
mindist = dist[j];
mindistindex = j;
}
}
visited[mindistindex] = true;//Add vertices to the visited array
// Update the shortest distance
for (int j = 0; j < x1.length; j + + ) {
if (!visited[j] & amp; & amp; x1[mindistindex][j] != 0 & amp; & amp; dist[mindistindex] != Integer.MAX_VALUE
& amp; & amp; dist[mindistindex] + x1[mindistindex][j] < dist[j]) {
dist[j] = dist[mindistindex] + x1[mindistindex][j];//Update the shortest distance
pre[j]=mindistindex + 1;//Record the predecessor node
}
}
}
System.out.printf("Vertex: ");
for (int i = 0; i < x1.length; i + + ) {
System.out.printf((i + 1) + " ");
}
System.out.println();
System.out.printf("Distance: ");
for (int i = 1; i < x1.length; i + + ) {
System.out.printf(dist[i] + " ");
}
System.out.println();
System.out.printf("Precursor: ");
for (int i = 1; i < x1.length; i + + ) {
System.out.printf(pre[i] + " ");
}
}
Run result:
Algorithm analysis:
time complexity:
- Initialization phase: All vertices need to be traversed, and the time complexity is O(n).
- Shortest path search phase: n iterations are required. Each iteration needs to traverse all vertices. The time complexity is O(n^2). Therefore, the overall time complexity is O(n^2).
Space complexity:
- Four arrays are used, of which x1 occupies O(n^2) space, dist, visited, and pre occupy O(n) space respectively. Therefore, the space complexity is O(n^2).
It should be noted that the analysis of time complexity and space complexity is based on the case where the size of the given graph is n. In practical applications, if the size of the graph is very large, you can consider using optimization algorithms or data structures to reduce time and space overhead.
Implementation of other programming languages:
Note: The following codes are all generated by AI. If readers find bugs, they can post them in the comment area and we will solve them together!
C language program:
#include <stdio.h>
#include <stdbool.h>
#include <limits.h>
#define SIZE 8 // Matrix size
void dijkstra(int graph[SIZE][SIZE], int source) {
int dist[SIZE]; // The shortest distance from the origin to each point
bool visited[SIZE]; //Record whether the node is visited
int pre[SIZE]; // Record the predecessor node of the shortest path
for (int i = 0; i < SIZE; i + + ) {
dist[i] = INT_MAX; // Initialized to infinity
visited[i] = false; // Initialized to have not been visited
pre[i] = -1; // The precursor is initialized to -1
}
dist[source - 1] = 0; // self to self is 0
// Find the distance from the origin to each vertex
for (int i = 0; i < SIZE; i + + ) {
int minDist = INT_MAX; // shortest path
int minDistIndex = -1; // Index of the shortest path
// Find the shortest path
for (int j = 0; j < SIZE; j + + ) {
if (!visited[j] & amp; & amp; dist[j] < minDist) {
minDist = dist[j];
minDistIndex = j;
}
}
visited[minDistIndex] = true; // Add vertices to the visited array
// Update the shortest distance
for (int j = 0; j < SIZE; j + + ) {
if (!visited[j] & amp; & amp; graph[minDistIndex][j] != 0 & amp; & amp; dist[minDistIndex] != INT_MAX & amp; & amp;
dist[minDistIndex] + graph[minDistIndex][j] < dist[j]) {
dist[j] = dist[minDistIndex] + graph[minDistIndex][j]; // Update the shortest distance
pre[j] = minDistIndex + 1; // Record the predecessor node
}
}
}
printf("Vertex: ");
for (int i = 0; i < SIZE; i + + ) {
printf("%d ", i + 1);
}
printf("\
");
printf("Distance: ");
for (int i = 1; i < SIZE; i + + ) {
printf("%d ", dist[i]);
}
printf("\
");
printf("Precursor: ");
for (int i = 1; i < SIZE; i + + ) {
printf("%d ", pre[i]);
}
}
int main() {
int graph[SIZE][SIZE] = {
{0, 2, 0, 1, 0, 3, 0, 0},
{0, 0, 6, 0, 5, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 6},
{0, 10, 0, 0, 0, 0, 2, 0},
{0, 0, 9, 0, 0, 0, 0, 4},
{0, 0, 0, 5, 0, 0, 4, 0},
{0, 7, 0, 0, 3, 0, 0, 8},
{0, 0, 0, 0, 0, 0, 0, 0}
};
int source = 1; // represents the origin
dijkstra(graph, source);
return 0;
}
python program:
import sys
def dijkstra(x1, s):
dist = [sys.maxsize] * len(x1) # represents the shortest distance from the origin to each point
visited = [False] * len(x1)
pre = [-1] * len(x1) # Record the predecessor node of the shortest path
dist[s - 1] = 0 # self to itself is 0
for _ in range(len(x1)):
mindist = sys.maxsize # shortest path
mindistindex = -1 # Index of the shortest path
# Find the shortest path
for j in range(len(x1)):
if not visited[j] and dist[j] < mindist:
# update data
mindist = dist[j]
mindistindex = j
visited[mindistindex] = True #Add vertices to the visited array
# Update the shortest distance
for j in range(len(x1)):
if not visited[j] and x1[mindistindex][j] != 0 and dist[mindistindex] != sys.maxsize and dist[mindistindex] + x1[mindistindex][j] < dist[j]:
dist[j] = dist[mindistindex] + x1[mindistindex][j] # Update the shortest distance
pre[j] = mindistindex + 1 # Record the predecessor node
print("Vertex:", end=" ")
for i in range(len(x1)):
print(i + 1, end=" ")
print()
print("Distance:", end=" ")
for i in range(1, len(x1)):
print(dist[i], end=" ")
print()
print("Precursor:", end=" ")
for i in range(1, len(x1)):
print(pre[i], end=" ")
print()
if __name__ == "__main__":
x1 = [[0, 2, 0, 1, 0, 3, 0, 0],
[0, 0, 6, 0, 5, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 6],
[0, 10, 0, 0, 0, 0, 2, 0],
[0, 0, 9, 0, 0, 0, 0, 4],
[0, 0, 0, 5, 0, 0, 4, 0],
[0, 7, 0, 0, 3, 0, 0, 8],
[0, 0, 0, 0, 0, 0, 0, 0]]
s = 1 # represents the origin
dijkstra(x1, s)
Note that there is no integer overflow problem in Python similar to that in Java, so
sys.maxsizeis used as infinity. In addition, Python’s index starts from 0, so both the vertex and index need to be increased by 1 when outputting. Hope this helps! If you have any other questions, please feel free to ask me.
C++ program:
#include<iostream>
using namespace std;
int main(){
int x1[8][8]={<!-- -->{0,2,0,1,0,3,0,0},
{0,0,6,0,5,0,0,0},
{0,0,0,0,0,0,0,6},
{0,10,0,0,0,0,2,0},
{0,0,9,0,0,0,0,4},
{0,0,0,5,0,0,4,0},
{0,7,0,0,3,0,0,8},
{0,0,0,0,0,0,0,0}};
int s=1;
const int n=8;
int dist[n],pre[n];
bool visited[n];
for(int i=0;i<n;i + + ){
dist[i]=INT_MAX;
visited[i]=false;
pre[i]=-1;
}
dist[s-1]=0;
for(int i=0;i<n;i + + ){
int mindist=INT_MAX,mindistindex=-1;
for(int j=0;j<n;j + + ){
if(!visited[j] & amp; & amp;dist[j]<mindist){
mindist=dist[j];
mindistindex=j;
}
}
visited[mindistindex]=true;
for(int j=0;j<n;j + + ){
if(!visited[j] & amp; & amp;x1[mindistindex][j]!=0 & amp; & amp;dist[mindistindex]!=INT_MAX & amp; & amp;dist[mindistindex] + x1[mindistindex ][j]<dist[j]){
dist[j]=dist[mindistindex] + x1[mindistindex][j];
pre[j]=mindistindex + 1;
}
}
}
cout<<"Vertex: ";
for(int i=0;i<n;i + + ){
cout<<i + 1<<" ";
}
cout<<endl;
cout<<"Distance: ";
for(int i=1;i<n;i + + ){
cout<<dist[i]<<" ";
}
cout<<endl;
cout<<"Precursor: ";
for(int i=1;i<n;i + + ){
cout<<pre[i]<<" ";
}
cout<<endl;
return 0;
}